Sort Algorithms#

As of version 5.07, Miva Script includes the built-in function miva_array_sort(). However, there are faster and educational sort routines provided below, ordered from slowest to fastest; the fastest take advantage of built-in Miva Script capabilities.

Included Sort Routines#

Bubble Sort (530 per second): Single dimension, text only, ascending only.
Insertion Sort (950 per second): Single dimension, text only, ascending only.
Quick Sort (2250 per second): Member-selectable, text or numbers, ascending or descending.
Array Sort By (5500 per second): Member-selectable, text or numbers, ascending or descending.
Miva_Array_Sort (8000 per second): Text only, ascending or descending.
Gieppner Sort (16000 per second): Member-selectable, text or numbers, ascending or descending; limited character set.
Member Sort (17500 per second): Single dimension text, ascending only; limited character set.
Radix Sort (19000 per second): Text, ascending or descending; smaller datasets even faster.
Binary Search (virtually instant): Searches sorted arrays up to millions of records in ~20 comparisons.

Note

Sorting rates are averages from randomized-text tests in Miva Mia; your mileage may vary.

Bubble Sort#

The “bubble” sort repeatedly steps through the list, compares adjacent items, and swaps them if out of order. Passes continue until no swaps occur. Coined by K.E. Iverson in 1962, it’s simple but not the fastest. Implementation by Ray Yates. Watch a video demo.

Relative speed: 530 elements/sec.

<MvFUNCTION NAME="Bubblesort" PARAMETERS="list" STANDARDOUTPUTLEVEL="">
  <!-- Simple single dimension bubble sort -->
  <MvCOMMENT>
    procedure bubbleSort(A : list of sortable items):
      do
        swapped := false
        for i = 0 to len(A)-2:
          if A[i] > A[i+1] then
            swap(A[i], A[i+1])
            swapped := true
          end if
        end for
      while swapped
  </MvCOMMENT>

  <MvASSIGN NAME="l.swapped" VALUE="{1}">
  <MvASSIGN NAME="l.maxlist" VALUE="{ miva_array_elements(l.list)-1 }">
  <MvWHILE EXPR="{ l.swapped }">
    <MvASSIGN NAME="l.swapped" VALUE="{0}">
    <MvASSIGN NAME="l.ndx" VALUE="{1}">
      <MvWHILE EXPR="{ l.ndx LE l.maxlist }">
        <MvIF EXPR="{ l.list[l.ndx] GT l.list[l.ndx+1] }">
          <!-- swap -->
          <MvASSIGN NAME="l.temp" VALUE="{ l.list[l.ndx] }">
          <MvASSIGN NAME="l.list" INDEX="{ l.ndx }" VALUE="{ l.list[l.ndx+1] }">
          <MvASSIGN NAME="l.list" INDEX="{ l.ndx+1 }" VALUE="{ l.temp }">
          <MvASSIGN NAME="l.swapped" VALUE="{1}">
        </MvIF>
        <MvASSIGN NAME="l.ndx" VALUE="{ l.ndx+1 }">
      </MvWHILE>
  </MvWHILE>

  <MvFUNCRETURN VALUE="{ l.list }">
</MvFUNCTION>

Insertion Sort#

Insertion sort builds a sorted list one item at a time by inserting each element into its correct position. Efficient for small or partially sorted lists. Implementation by Ray Yates. See a video.

Relative speed: 950 elements/sec.

<MvFUNCTION NAME="Insertionsort" PARAMETERS="list" STANDARDOUTPUTLEVEL="">
  <MvCOMMENT>
    insertionSort(A):
      for i = 1 to len(A)-1:
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
          A[j+1] = A[j]
          j = j - 1
        end while
        A[j+1] = key
      end for
  </MvCOMMENT>

  <MvASSIGN NAME="l.maxlist" VALUE="{ miva_array_elements(l.list) }">
  <MvASSIGN NAME="l.i" VALUE="{2}">
  <MvWHILE EXPR="{ l.i LE l.maxlist }">
    <MvASSIGN NAME="l.key" VALUE="{ l.list[l.i] }">
    <MvASSIGN NAME="l.j" VALUE="{ l.i - 1 }">
      <MvWHILE EXPR="{ (l.j GE 1) AND (l.list[l.j] GT l.key) }">
        <MvASSIGN NAME="l.list" INDEX="{ l.j+1 }" VALUE="{ l.list[l.j] }">
        <MvASSIGN NAME="l.j" VALUE="{ l.j - 1 }">
      </MvWHILE>
    <MvASSIGN NAME="l.list" INDEX="{ l.j+1 }" VALUE="{ l.key }">
    <MvASSIGN NAME="l.i" VALUE="{ l.i + 1 }">
  </MvWHILE>

  <MvFUNCRETURN VALUE="{ l.list }">
</MvFUNCTION>

Quick Sort#

QuickSortArray is a divide-and-conquer implementation by Tony Hoare (1960), built into the Miva Merchant API by Jonathan Burchmore. It partitions around a pivot, sorting subarrays recursively.

Relative speed: 2250 elements/sec.

<!-- Main entry -->
<MvFUNCTION NAME="QuickSortArray" PARAMETERS="array var, subelement, direction">
  <!-- prepare comparisons -->
  <MvASSIGN NAME="l.comparisons" INDEX="1" MEMBER="subelement" VALUE="{ l.subelement }">
  <MvASSIGN NAME="l.comparisons" INDEX="1" MEMBER="direction" VALUE="{ l.direction }">
  <!-- sort full array -->
  <MvEVAL EXPR="{ QuickSortArray_Sort( l.array, 1, miva_array_elements(l.array), l.comparisons, 1 ) }">
</MvFUNCTION>

<!-- Recursive sort -->
<MvFUNCTION NAME="QuickSortArray_Sort" PARAMETERS="array var, left, right, comparisons var, comparison_count">
  <MvIF EXPR="{ l.right LE l.left }"><MvFUNCTIONRETURN></MvFUNCTIONRETURN></MvIF>
  <MvASSIGN NAME="l.pivot_index" VALUE="{ QuickSortArray_Partition( l.array, l.left, l.right, l.left, l.comparisons, l.comparison_count ) }">
  <MvEVAL EXPR="{ QuickSortArray_Sort( l.array, l.left, l.pivot_index-1, l.comparisons, l.comparison_count ) }">
  <MvEVAL EXPR="{ QuickSortArray_Sort( l.array, l.pivot_index+1, l.right, l.comparisons, l.comparison_count ) }">
</MvFUNCTION>

<!-- Partition helper -->
<MvFUNCTION NAME="QuickSortArray_Partition" PARAMETERS="array var, left, right, pivot_index, comparisons var, comparison_count">
  <MvASSIGN NAME="l.pivot_element" VALUE="{ l.array[l.pivot_index] }">
  <MvASSIGN NAME="l.store_index" VALUE="{ l.left }">
  <MvEVAL EXPR="{ QuickSortArray_Swap( l.array, l.pivot_index, l.right ) }">
  <MvASSIGN NAME="l.i" VALUE="{ l.left }">
  <MvWHILE EXPR="{ l.i LT l.right }">
    <MvIF EXPR="{ QuickSortArray_Compare( l.array[l.i], l.pivot_element, l.comparisons, l.comparison_count ) LE 0 }">
      <MvEVAL EXPR="{ QuickSortArray_Swap( l.array, l.i, l.store_index ) }">
      <MvASSIGN NAME="l.store_index" VALUE="{ l.store_index+1 }">
    </MvIF>
    <MvASSIGN NAME="l.i" VALUE="{ l.i+1 }">
  </MvWHILE>
  <MvEVAL EXPR="{ QuickSortArray_Swap( l.array, l.store_index, l.right ) }">
  <MvFUNCTIONRETURN VALUE="{ l.store_index }">
</MvFUNCTION>

<!-- Compare helper -->
<MvFUNCTION NAME="QuickSortArray_Compare" PARAMETERS="left_element var, right_element var, comparisons var, comparison_count">
  <MvASSIGN NAME="l.comp_pos" VALUE="{1}">
  <MvWHILE EXPR="{ l.comp_pos LE l.comparison_count }">
    <MvASSIGN NAME="l.left_value" VALUE="{ miva_variable_value('l.left_element'$l.comparisons[l.comp_pos]:subelement) }">
    <MvASSIGN NAME="l.right_value" VALUE="{ miva_variable_value('l.right_element'$l.comparisons[l.comp_pos]:subelement) }">
    <MvIF EXPR="{ l.left_value LT l.right_value }"><MvFUNCTIONRETURN VALUE="{ 0 - l.comparisons[l.comp_pos]:direction }"></MvFUNCTIONRETURN></MvIF>
    <MvELSEIF EXPR="{ l.left_value GT l.right_value }"><MvFUNCTIONRETURN VALUE="{ l.comparisons[l.comp_pos]:direction }"></MvFUNCTIONRETURN></MvELSEIF>
    <MvASSIGN NAME="l.comp_pos" VALUE="{ l.comp_pos+1 }">
  </MvWHILE>
  <MvFUNCTIONRETURN VALUE="0">
</MvFUNCTION>

<!-- Swap helper -->
<MvFUNCTION NAME="QuickSortArray_Swap" PARAMETERS="array var, a, b">
  <MvASSIGN NAME="l.temp" VALUE="{ l.array[l.a] }">
  <MvASSIGN NAME="l.array" INDEX="{ l.a }" VALUE="{ l.array[l.b] }">
  <MvASSIGN NAME="l.array" INDEX="{ l.b }" VALUE="{ l.temp }">
</MvFUNCTION>

Array Sort By#

Adaptation of miva_array_sort() to sort structured arrays by a chosen member. Originally by Scott McCollough, optimized by Ray Yates.

Relative speed: 5500 elements/sec.

<MvFUNCTION NAME="Array_Sort_By" PARAMETERS="digits, orderby, member, array var">
  <MvCOMMENT>
    Based on Miva_Array_Sort_By() by Scott McCollough; optimized by Ray Yates.
    Digits: pad length for numeric sort.
    Orderby: 'D' descending, 'A' ascending.
    Member: array member name.
  </MvCOMMENT>
  <!-- build sort key 'A' on each element -->
  <MvASSIGN NAME="l.max" VALUE="{ miva_array_max(l.array) }">
  <MvASSIGN NAME="l.pos" VALUE="{ miva_array_min(l.array) }">
  <MvIF EXPR="{ l.digits }">
    <MvWHILE EXPR="{ l.pos LE l.max }">
      <MvASSIGN NAME="l.array" INDEX="{ l.pos }" MEMBER="A"
                VALUE="{ padl(miva_variable_value('l.array['$l.pos$']:'$l.member), l.digits, '0') }">
      <MvASSIGN NAME="l.pos" VALUE="{ miva_array_next(l.array, l.pos) }">
    </MvWHILE>
  <MvELSE>
    <MvWHILE EXPR="{ l.pos LE l.max }">
      <MvASSIGN NAME="l.array" INDEX="{ l.pos }" MEMBER="A"
                VALUE="{ miva_variable_value('l.array['$l.pos$']:'$l.member) }">
      <MvASSIGN NAME="l.pos" VALUE="{ miva_array_next(l.array, l.pos) }">
    </MvWHILE>
  </MvIF>
  <!-- perform sort -->
  <MvIF EXPR="{ l.orderby EQ 'D' }">
    <MvASSIGN NAME="l.count" VALUE="{ miva_array_sort(l.array, 'MA_Sort_Desc', l.null) }">
  <MvELSE>
    <MvASSIGN NAME="l.count" VALUE="{ miva_array_sort(l.array, 'MA_Sort_Asc', l.null) }">
  </MvIF>
  <MvFUNCTIONRETURN VALUE="{ l.count }">
</MvFUNCTION>

Miva_Array_Sort#

Built-in bubble sort (miva_array_sort()), implemented by Mark Johnson. Uses user-supplied compare functions.

Relative speed: 8000 elements/sec.

<!-- Ascending -->
<MvASSIGN NAME="l.count" VALUE="{ miva_array_sort(l.array, 'MA_Sort_Asc', l.data) }">
<MvFUNCTION NAME="MA_Sort_Asc" PARAMETERS="left var, right var, data var">
  <MvIF EXPR="{ l.left LT l.right }"><MvFUNCTIONRETURN VALUE="-1"></MvFUNCTIONRETURN></MvIF>
  <MvELSEIF EXPR="{ l.left GT l.right }"><MvFUNCTIONRETURN VALUE="1"></MvFUNCTIONRETURN></MvELSEIF>
  <MvFUNCTIONRETURN VALUE="0">
</MvFUNCTION>

<!-- Descending -->
<MvASSIGN NAME="l.count" VALUE="{ miva_array_sort(l.array, 'MA_Sort_DESC', l.data) }">
<MvFUNCTION NAME="MA_Sort_Desc" PARAMETERS="left var, right var, data var">
  <MvIF EXPR="{ l.left LT l.right }"><MvFUNCTIONRETURN VALUE="1"></MvFUNCTIONRETURN></MvIF>
  <MvELSEIF EXPR="{ l.left GT l.right }"><MvFUNCTIONRETURN VALUE="-1"></MvFUNCTIONRETURN></MvELSEIF>
  <MvFUNCTIONRETURN VALUE="0">
</MvFUNCTION>

Gieppner Sort#

Optimized splay-tree sort by Marcus Gieppner (MvMarkus), improved by Ray Yates. Limited to alphanumeric + underscore.

Relative speed: 16000 elements/sec.

<MvFUNCTION NAME="Gieppner_Sort" PARAMETERS="number, direction, element, array VAR, returnarray VAR">
  <MvCOMMENT>
    Numeric sort if number>0 (padding), else text.
    Direction: 'D' or 'A'. Element: array member.
  </MvCOMMENT>
  <!-- build index based on asciichar and splay-tree -->
  <MvASSIGN NAME="l.max" VALUE="{ miva_array_max(l.array) }">
  <MvASSIGN NAME="l.pos" VALUE="{ miva_array_min(l.array) }">
  <!-- ...build index structure... -->
  <MvASSIGN NAME="l.index" VALUE="{ miva_array_deserialize(trim(l.index)) }">
  <!-- output sorted based on index and direction -->
  <!-- ... -->
</MvFUNCTION>

Member Sort#

Fastest text-only sort using Miva Script’s splay-tree array member ordering. Developed by Marcus Gieppner.

Relative speed: 17500 elements/sec.

<MvFUNCTION NAME="Member_Sort" PARAMETERS="array var, sorted var">
  <MvCOMMENT>
    Only ascendant text sort; leverages member ordering.
  </MvCOMMENT>
  <MvASSIGN NAME="l.a" VALUE="{1}">
  <MvASSIGN NAME="l.max" VALUE="{ miva_array_max(l.array) }">
  <MvWHILE EXPR="{ l.a LE l.max }">
    <MvIF EXPR="{ l.array[l.a] }">
      <MvASSIGNARRAY NAME="l.sorted_array" VALUE="{ l.array[l.a] }">
        <MvMEMBER NAME="{ l.array[l.a] }">
        <MvDIMENSION INDEX="{ miva_array_max(miva_variable_value('l.sorted_array:'$l.array[l.a]))+1 }">
      </MvASSIGNARRAY>
    </MvIF>
    <MvASSIGN NAME="l.a" VALUE="{ l.a+1 }">
  </MvWHILE>
  <MvASSIGN NAME="l.sorted" VALUE="{ miva_array_deserialize(trim(l.sorted_array)) }">
</MvFUNCTION>

Radix Text Sort#

Modified Radix sort by Ray Yates for text, no comparisons—indexes by character codes recursively.

Relative speed: 19800 elements/sec.

<MvFUNCTION NAME="Radix_Sort" PARAMETERS="direction, array var, sorted var">
  <MvCOMMENT>
    Recursive table-based radix sort by character position.
  </MvCOMMENT>
  <!-- build letterTable by first char -->
  <MvFOREACH ITERATOR="l.item" ARRAY="l.array" INDEX="l.pos">
    <MvASSIGNNAME="l.charcode" VALUE="{ asciivalue(substring(l.item,1,1)) }">
    <!-- ... -->
  </MvFOREACH>
  <!-- recursive ys_matrix_row calls -->
  <!-- ... -->
  <!-- output sorted based on direction -->
</MvFUNCTION>

Binary Search#

Efficient half-interval search over sorted arrays. Coded by Ray Yates. Returns index if found, else 0.

Relative speed: virtually instant.

<MvFUNCTION NAME="BinarySearch_By" PARAMETERS="a var, member, key">
  <MvASSIGN NAME="l.low" VALUE="{1}">
  <MvASSIGN NAME="l.high" VALUE="{ miva_array_elements(a) }">
  <MvWHILE EXPR="{ l.low LE l.high }">
    <MvASSIGN NAME="l.mid" VALUE="{ int((l.low + l.high)/2) }">
    <!-- fetch element -->
    <MvREFERENCEARRAY NAME="l.element" VARIABLE="a">
      <MvDIMENSION INDEX="{ l.mid }">
      <MvMEMBER NAME="{ l.member }">
    </MvREFERENCEARRAY>
    <MvIF EXPR="{ l.element GT key }">
      <MvASSIGN NAME="l.high" VALUE="{ l.mid - 1 }">
    <MvELSEIF EXPR="{ l.element LT key }">
      <MvASSIGN NAME="l.low" VALUE="{ l.mid + 1 }">
    <MvELSE>
      <MvASSIGN NAME="l.found" VALUE="{ l.mid }">
      <MvWHILESTOP>
    </MvIF>
  </MvWHILE>
  <MvFUNCRETURN VALUE="{ l.found }">
</MvFUNCTION>