Linearithmic Sorts
We add another sorting strategy, the Quicksort, to our repertoire of linearithmic sorts.
| Name | Description | Average Case |
|---|---|---|
| Heapsort | Build 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-1$ times. | $O(n \lg n)$ |
| Merge Sort | Divide the sequence into subsequences of singletons. Successively merge the subsequences pairwise until a single sequence is reformed. | $O(n\lg n)$ |
| Quicksort | Pick 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(n\lg n)$ |
As noted here, "quicksort has running time $O(n^2)$ in the worst case, but it is typically $O(n \lg n)$. Indeed, in practical situations, a finely tuned implementation of quicksort beats most sorting algorithms, including those whose theoretical complexity is $O(n \lg n)$ in the worst case.