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 \;\Longrightarrow\; 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.