# January 13, 2003

#### A Comparison of Sorting Algorithms

ethods for sorting have been intensively studied and optimized.

#### QuickSort—Exploiting the Principle of Exchanging Keys

‘ 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

#### MSD RadixSort – An algorithm that can achieve O(N) behavior

‘ 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,

#### InsertionSort – A simple routine with minimal overhead

‘ 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

#### Ternary QuickSort – A modification of QuickSort

‘ 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

#### ShuttleMergeSort – An improved MergeSort

‘ 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

#### SelectionSort – Short, simple and sloooow

‘ 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

#### MergeSort – A stable sort

‘ MergeSort. A stable sort (preserves original order of records with equal ‘ keys). Like HeapSort, easily adapted to any data type and guaranteed to run ‘ in O(N log

#### HeapSort – A compact routine that sorts data in place

‘ HeapSort. A compact routine that sorts data in place (no extra memory needed)’ and is guaranteed to run in O(N log N) time no matter how the input data