The Comparison Lower Bound on Sorting

Merge sort and heap sort both run in $O(n \log n)$ time, and a natural interview follow-up is: can a cleverer algorithm do better? For any algorithm that sorts purely by comparing pairs of elements (asking "is $a < b$?" and nothing else), the answer is no — $n \log n$ comparisons, up to a constant factor, is provably the best possible in the worst case, for any input size $n$.

The proof is a counting argument, not an algorithmic one. Any comparison-based sorting algorithm can be modelled as a decision tree: each internal node is one comparison, each branch is one possible outcome, and each leaf corresponds to one final, fully determined ordering of the input. For $n$ distinct elements there are $n!$ possible orderings, and the algorithm must be able to reach a distinct leaf for every one of them — a tree with fewer than $n!$ leaves would have two different true orderings mapping to the same leaf, meaning the algorithm couldn't tell them apart. A binary tree with $n!$ leaves must have depth at least $\log_2(n!)$, and by Stirling's approximation $\log_2(n!) \approx n \log_2 n - n/\ln 2$, which is $\Theta(n \log n)$. Since the tree's depth is exactly the worst-case number of comparisons the algorithm might need, no comparison-based algorithm can have worst-case comparisons below $\Theta(n \log n)$.

For $n = 4$ elements there are $4! = 24$ possible orderings, requiring $\lceil \log_2 24 \rceil = 5$ comparisons in the worst case at minimum — matching what insertion sort or merge sort actually need on 4 elements, confirming the bound is tight, not just a loose estimate.