Comparison sort lower bound

Remarks

The proof models $\mathcal{A}$ on inputs of size $n$ as a decision tree: a binary tree whose internal nodes are comparisons and whose leaves are outputs. The $n!$ orderings of distinct elements need $n!$ different outputs, so the tree has at least $n!$ leaves. A binary tree of height $h$ has at most $2^h$ leaves, so $h \ge \log_2(n!)$, and the height is the worst-case number of comparisons. For the average, a binary tree with $L$ leaves has average leaf depth at least $\log_2 L$. The estimate of $\log_2(n!)$ follows from Stirling's formula.

Example: for $n = 3$, $\ceil{\log_2 6} = 3$, so no comparison sort sorts every list of $3$ distinct items with $2$ comparisons; $2$ comparisons give only $4$ possible outcomes, fewer than the $6$ orderings. Merge sort uses $O(n \log n)$ comparisons, so the bound is optimal up to a constant factor.

The hypothesis that only comparisons are used is necessary. Counting sort sorts $n$ integers in $\set{1, \dots, k}$ in $O(n + k)$ steps, which is $O(n)$ when $k = O(n)$, by using the values themselves as array indices.

Going deeper

For a student

This is the standard example of a lower bound in a restricted model of computation, the decision tree model. It shows that merge sort and heapsort are asymptotically optimal among comparison sorts. The average case of randomized quicksort, about $1.39\, n \log_2 n$ comparisons, is within a constant factor of optimal. The same counting argument shows that finding an element in a sorted list by comparisons needs about $\log_2 n$ steps, matching binary search.