January 13, 2003

Option ExplicitOption Compare BinaryOption Base 1Public Type TRIAL nKEYS As Long nITS As Integer PT As Long TT As Long ST As LongEnd TypePublic Const RAD = 1Public Const TQK = 2Public Const QUI = 3Public Const MER = 4Public Const HEA = 5Public Const COM = 6Public Const SHE

‘ ShellSort. A compact routine that sorts data in place (no extra memory ‘ needed) and runs in O(N (log N)^2) time. Not stable (does not preserve ‘ original order of records with equal keys).’ Like InsertionSort, works by taking a key from the right side of the list and

‘ QuickSort. QuickSort, CombSort and ShellSort all exploit the principle of ‘ exchanging keys that are far apart in the list rather than adjacent. ‘ QuickSort does this most elegantly and rapidly. The approach is to choose a ‘ “pivot” value (ideally, the median key) and then to work from

‘ MSD RadixSort. No sort based on comparisons can be faster than O(N log N). ‘ RadixSort makes no comparisons and can therefore achieve O(N) behavior. To ‘ do this, it examines keys one byte at a time, counting the number of keys ‘ that have each possible byte value.

‘ InsertionSort. A simple routine with minimal overhead. Should never be used ‘ to sort long lists because of its O(N^2) behavior,’ but is the method of choice for sorting short (5-50 key) lists or long lists ‘ that have been mostly sorted by a faster algorithm. InsertionSort is faster

‘ Ternary QuickSort. See the summary of QuickSort for background before ‘ reading this one. Ternary QuickSort (also called MultiKey QuickSort) differs ‘ from the original QuickSort by examining keys one byte at a time (like ‘ RadixSort), and by handling keys in three categories — less than pivot,’ equal

‘ 2/4/03. The previous version of ShuttleMergeSort failed on very short lists. ‘ The code below corrects the problem and eliminates a couple of unnecessary ‘ variables. Sorting times for one million random longs,’ double or strings are 67, 90 and 95 seconds (Excel 2001 / 800 mhz PowerBook /’

‘ SelectionSort. Short, simple and sloooow. This is another O(N^2) sort that ‘ should never be used on long lists. Like InsertionSort,’ it needs no extra memory (in place) and preserves the existing order of ‘ records with equal keys. Unfortunately, it’s slower,’ and there’s no reason to use it