Sorting Lower Bounds
We've seen that merge sort and heap sort run in $O(n \log n)$. Can we do better? The answer is no, for comparison-based sorting algorithms. This is one of the most elegant proofs in computer science.
The Question
A comparison-based sorting algorithm can only access elements through comparisons: "is $a_i < a_j$?" It cannot look at the actual values of elements (unlike counting sort or radix sort).
Claim: Any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the worst case.
The Decision Tree Model
Model any comparison-based algorithm as a binary decision tree:
- Each internal node is a comparison "$a_i < a_j$?".
- The left child is the path taken if yes; right child if no.
- Each leaf represents a specific permutation (output order).
For the algorithm to be correct, it must be able to produce every possible permutation as output. There are $n!$ permutations of $n$ elements, so the tree must have at least $n!$ leaves.
The Proof
Step 1: Relate tree height to number of leaves
A binary tree of height $h$ has at most $2^h$ leaves. So if the tree has $\geq n!$ leaves:
$$2^h \geq n! \implies h \geq \log_2(n!)$$Step 2: Apply Stirling's approximation
Stirling's approximation states:
$$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$Taking the logarithm:
$$\log_2(n!) = \log_2\left(\sqrt{2\pi n}\right) + n\log_2\left(\frac{n}{e}\right)$$ $$= \frac{1}{2}\log_2(2\pi n) + n\log_2 n - n\log_2 e$$ $$= n\log_2 n - n\log_2 e + O(\log n)$$ $$= \Theta(n \log n)$$Step 3: Conclude
$$h \geq \log_2(n!) = \Theta(n \log n)$$The height of the decision tree is the worst-case number of comparisons. Therefore, any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the worst case. ✔
A Simpler Bound (without Stirling)
Even without Stirling, we can show $\log_2(n!) = \Omega(n \log n)$:
$$n! = n \cdot (n-1) \cdot (n-2) \cdots 1 \geq \left(\frac{n}{2}\right)^{n/2}$$(The top $n/2$ terms are each $\geq n/2$.)
$$\log_2(n!) \geq \frac{n}{2} \cdot \log_2\frac{n}{2} = \frac{n}{2}(\log_2 n - 1) = \Omega(n \log n) \quad \checkmark$$Complexity of All Major Sorts
| Algorithm | Best | Average | Worst | Space | Stable? | Comparison? |
|---|---|---|---|---|---|---|
| Bubble sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |
| Selection sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | Yes |
| Insertion sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |
| Merge sort | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | Yes | Yes |
| Quicksort | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | No | Yes |
| Heap sort | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | No | Yes |
| Counting sort | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(k)$ | Yes | No |
| Radix sort | $O(d(n+k))$ | $O(d(n+k))$ | $O(d(n+k))$ | $O(n+k)$ | Yes | No |
| Bucket sort | $O(n+k)$ | $O(n+k)$ | $O(n^2)$ | $O(n+k)$ | Yes | No |
The last three (counting, radix, bucket) are not comparison-based. They exploit the structure of the data (integer values, bounded range) and can beat $O(n \log n)$. The $\Omega(n \log n)$ lower bound only applies to comparison-based sorts.
Which Sorts Are Optimal?
A comparison-based sort is optimal if its worst-case complexity matches the lower bound: $\Theta(n \log n)$.
- Merge sort: Optimal. $O(n \log n)$ worst case. But uses $O(n)$ extra space.
- Heap sort: Optimal. $O(n \log n)$ worst case. $O(1)$ extra space. But poor cache locality.
- Quicksort: NOT optimal worst case ($O(n^2)$). But $O(n \log n)$ expected (average). Fastest in practice due to cache friendliness.
- Introsort (C++ std::sort): Starts as quicksort, switches to heap sort if recursion depth exceeds $2\log n$. Guarantees $O(n \log n)$ worst case.
Breaking the Barrier: Non-Comparison Sorts
Counting sort: $O(n + k)$
If values are integers in $[0, k)$, count occurrences and reconstruct. Time is $O(n + k)$. When $k = O(n)$, this is $O(n)$, beating $n \log n$.
Radix sort: $O(d \cdot (n + k))$
Sort $d$-digit numbers, one digit at a time (using counting sort as a subroutine). For $d = O(\log n)$ and $k = O(n)$, this is $O(n \log n)$. For fixed-width integers (e.g., 32-bit), $d$ is constant, giving $O(n)$.
Why don't we always use radix sort?
- Only works for integers (or things that can be represented as fixed-width keys).
- Poor cache locality for large $k$.
- The constant factor is often larger than quicksort's.
- Not in-place (needs $O(n + k)$ extra space).
Summary
- Any comparison-based sort needs $\Omega(n \log n)$ comparisons in the worst case.
- The proof uses the decision tree model: $n!$ leaves require height $\geq \log_2(n!) = \Theta(n \log n)$.
- Stirling's approximation: $\log_2(n!) = n \log_2 n - n \log_2 e + O(\log n) = \Theta(n \log n)$.
- Merge sort and heap sort are optimal comparison sorts.
- Counting sort and radix sort break the barrier by exploiting value structure, not comparisons.