Name	Best	Average	Worst	Memory	Stable	Method	Other Notes
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.