| Quicksort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{yellow}{\large \log n}$ |
No |
Partitioning |
Quicksort is usually done in-place with $\large O(\log n)$ stack space. |
| Merge sort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n}$ |
Yes |
Merging |
Highly parallelizable (up to $\large O(\log n)$ using the Three Hungarians' Algorithm). |
| In-place merge sort |
— |
— |
$\textcolor{yellow}{\large n \log^2 n}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Merging |
Can be implemented as a stable sort based on stable in-place merging. |
| Introsort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{yellow}{\large \log n}$ |
No |
Partitioning & Selection |
Used in several STL implementations. |
| Heapsort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large 1}$ |
No |
Selection |
|
| Insertion sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Insertion |
$\large O(n + d)$, in the worst case over sequences that have $d$ inversions. |
| Block sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Insertion & Merging |
Combine a block-based $\large O(n)$ in-place merge algorithm with a bottom-up merge sort. |
| Timsort |
$\textcolor{lime}{\large n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n}$ |
Yes |
Insertion & Merging |
Makes $n-1$ comparisons when the data is already sorted or reverse sorted. |
| Selection sort |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
No |
Selection |
Stable with $\large O(n)$ extra space, when using linked lists, or as a variant of Insertion Sort. |
| Shellsort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{yellow}{\large n^{4/3}}$ |
$\textcolor{yellow}{\large n^{3/2}}$ |
$\textcolor{lime}{\large 1}$ |
No |
Insertion |
Small code size. |
| Bubble sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Exchanging |
Tiny code size. |
| Exchange sort |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Exchanging |
Tiny code size. |
| Tree sort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n}$ |
Yes |
Insertion |
When using a self-balancing binary search tree. |
| Cycle sort |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
No |
Selection |
In-place with theoretically optimal number of writes. |
| Library sort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large n}$ |
No |
Insertion |
Similar to a gapped insertion sort. Random permutation needed for high-probability bounds, not stable. |
| Patience sorting |
$\textcolor{lime}{\large n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n}$ |
No |
Insertion & Selection |
Finds all the longest increasing subsequences in $\large O(n \log n)$. |
| Smoothsort |
$\textcolor{lime}{\large n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large 1}$ |
No |
Selection |
Adaptive variant of heapsort using the Leonardo sequence rather than a traditional binary heap. |
| Strand sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large n}$ |
Yes |
Selection |
|
| Tournament sort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{lime}{\large n}$ |
No |
Selection |
Variation of Heapsort. |
| Cocktail shaker sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Exchanging |
A variant of Bubblesort which deals well with small values at the end of the list. |
| Comb sort |
$\textcolor{lime}{\large n \log n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
No |
Exchanging |
Faster than bubble sort on average. |
| Gnome sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Exchanging |
Tiny code size. |
| Odd–even sort |
$\textcolor{lime}{\large n}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{red}{\large n^2}$ |
$\textcolor{lime}{\large 1}$ |
Yes |
Exchanging |
Can be run on parallel processors easily. |
