Linearithmic Sorts

  • Summary of Linearithmic Sorts.

We add another sorting strategy, the Quicksort, to our repertoire of linearithmic sorts.

NameDescriptionAverage Case
HeapsortBuild a max-heap from the sequence (bottom-up heapify). Remove the max and swap it to the end of the collection where the "leaf" was removed. Repeat the last step n−1n-1 times.O(nlg⁡n)\Omicron(n \lg n)
Merge SortDivide the sequence into subsequences of singletons. Successively merge the subsequences pairwise until a single sequence is reformed.O(nlg⁡n)\Omicron(n\lg n)
QuicksortPick an element from the sequence (the pivot), partition the remaining elements into those greater than and less than this pivot. Repeat this for each partition (recursively).O(nlg⁡n)\Omicron(n\lg n)

As noted here, "quicksort has running time O(n2)\Omicron(n^2) in the worst case, but it is typically O(nlg⁡n)\Omicron(n \lg n). Indeed, in practical situations, a finely tuned implementation of quicksort beats most sorting algorithms, including those whose theoretical complexity is O(nlg⁡n)\Omicron(n \lg n) in the worst case.