The Ω(n lg n) comparison-sort lower bound

Why can't we beat $n\lg n$ by comparing?

Insertion sort, merge sort, heapsort, and quicksort are all comparison sorts: they learn the order only by asking questions of the form "$a_i\le a_j$?" — they never look at the values themselves. This lesson proves a hard limit: any comparison sort needs $\Omega (n\lg n)$ comparisons in the worst case. It's not a failure of cleverness — it's information-theoretic.

The decision-tree model

Model a comparison sort as a decision tree: a full binary tree where each internal node is a comparison "$i:j$", the left branch is taken when $a_i\le a_j$ and the right when $a_i>a_j$, and each leaf is the permutation the algorithm outputs along that path. Running the algorithm on one input = tracing one root-to-leaf path; the number of comparisons on that input = the path length. The worst-case comparison count is the tree's height $h$.

The proof (Theorem 8.1)

A correct sort must produce all $n!$ orderings, so the tree needs at least $n!$ reachable leaves. A binary tree of height $h$ has at most $2^h$ leaves. Combining:

$$n!\le (\text{leaves})\le 2^h⟹h\ge \lg (n!)=\Theta (n\lg n),$$

where $\lg (n!)=\Theta (n\lg n)$ is Stirling's approximation. Hence $h=\Omega (n\lg n)$: every comparison sort makes $\Omega (n\lg n)$ comparisons in the worst case. Each comparison yields at most one bit ("$\le$" or "$>$"), and distinguishing $n!$ outcomes needs $\ge \lg (n!)$ bits — that is the deep reason.

What it buys us

Corollary: merge sort and heapsort run in $O(n\lg n)$ (matching the bound), so they are asymptotically optimal comparison sorts — no comparison-based method can do better than a constant factor. The bound is model-specific: it constrains only comparison sorts. The next lesson breaks $\Omega (n\lg n)$ by not comparing.

Worked example

For $n=3$: $3!=6$, and a binary tree needs height $\ge \lceil \lg 6\rceil =3$ to hold 6 leaves — so 3 elements need at least 3 comparisons in the worst case, which insertion sort exactly achieves.