The Sorting Lower Bound
Any sort that orders by comparing keys must make at least on the order of n log n comparisons in the worst case.
Sorting as a decision tree
Model any comparison-based sort as a binary decision tree: each internal node is a comparison of two keys, and the two branches are the yes and no outcomes. Every distinct sorted arrangement the algorithm can produce must correspond to a leaf, because the algorithm's behaviour is fully determined by the comparison results.
Counting the leaves
There are n! possible orderings of n distinct elements, so the tree needs at least n! leaves to sort every input correctly. A binary tree of height h has at most 2^h leaves, so 2^h must be at least n!. Taking logarithms, h is at least log2(n!).
From n! to n log n
By Stirling's approximation, log2(n!) is on the order of n log n. Since the height of the decision tree equals the worst-case number of comparisons the algorithm makes, every comparison sort needs Omega(n log n) comparisons in the worst case. This is a hard limit that no clever comparison sort can beat.
- n! orderings force at least n! leaves
- Tree height h satisfies 2^h >= n!
- h >= log2(n!) = Omega(n log n)
- Merge sort and heapsort meet this bound
How linear sorts escape it
The bound applies only to algorithms whose sole tool is comparing keys. Counting sort and radix sort instead use the key values directly as array indices or digits, so they are not comparison sorts and can run in linear time. They pay for this with restrictions on the key type and range.