
A Comparison of Sorting Algorithms
ethods for sorting have been intensively studied and optimized.
ethods for sorting have been intensively studied and optimized.
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