the comparison-sorting lower bound
Merge sort and heapsort both run in O(n log n), and for decades nobody found a comparison sort that was fundamentally faster. The comparison-sorting lower bound explains why this is not bad luck: it proves that ANY algorithm that sorts by comparing keys must make Omega(n log n) comparisons in the worst case. The familiar O(n log n) sorts are not just good; they are essentially optimal in their model.
The proof is a short, beautiful counting argument using the decision-tree model. Sorting n distinct items means deciding which of the n! possible orderings is the true one. Picture the algorithm as a binary decision tree: each internal node is a comparison, each leaf announces one ordering. To be correct, every one of the n! orderings must appear at some leaf, so the tree has at least n! leaves. A binary tree with L leaves has height at least log2(L). Therefore the worst-case number of comparisons — the tree's height — is at least log2(n!). Finally, by Stirling's estimate, log2(n!) is about n log2(n) - 1.44 n, which is Theta(n log n). So height >= log2(n!) = Omega(n log n), and that is the bound.
Two clarifications keep this honest. First, the bound is for the comparison model only: counting sort, radix sort, and bucket sort can run in O(n) because they exploit the keys' actual values or digits, stepping outside comparisons — they do not refute the theorem, they leave its arena. Second, this is a WORST-CASE bound on comparisons; particular inputs (an already-sorted array fed to insertion sort) can be much cheaper, and the bound says nothing about those easy cases. Because the upper bound O(n log n) and this lower bound Omega(n log n) coincide, comparison sorting is one of the rare problems whose complexity is exactly pinned down: Theta(n log n).
For n = 4, there are 4! = 24 orderings, so any comparison sort's decision tree needs >= 24 leaves and height >= ceil(log2(24)) = 5. Indeed no comparison sort can always sort 4 items in 4 comparisons; the worst case needs 5. The counting argument predicts the exact floor.
n! orderings force n! leaves; a binary tree with that many leaves is at least log2(n!) = Omega(n log n) tall.
It does not say sorting always needs n log n steps — only comparison sorts, only in the worst case. Linear-time sorts (radix, counting) are real and correct; they simply do not work by comparing keys, so they are outside the theorem.