Lower Bounds for Comparison Sorting

Mergesort, heapsort, and (in expectation) quicksort all run in $Θ (n log n)$ . Insertion sort and the rest do worse. None does better. It is natural to ask whether some cleverer algorithm could break the $n log n$ barrier. The striking answer is no, not if it learns about the input only by comparing elements. This lesson proves a matching lower bound: any comparison sort needs $Ω (n log n)$ comparisons in the worst case.¹ This is one of the rare cases where we can prove a problem hard, pinning its complexity from both sides.

The comparison model

A comparison sort determines the sorted order using only comparisons between pairs of input elements. The only questions it may ask are of the form is $a_{i} \leq a_{j}$ ? (or $<$ , $\geq$ , $>$ , $=$ ). It never inspects the elements' values; it cannot read a digit, hash a key, or use one as an array index. All of insertion, merge, quick, and heap sort live in this model, and so does almost every general-purpose sort.

This restriction is exactly what makes a lower bound possible. Because the only information the algorithm extracts is the outcomes of comparisons, we can account for everything it could possibly learn by counting those outcomes. The elements' actual values are irrelevant beyond their relative order, so we may assume without loss of generality that the input is some permutation of the distinct values ${1, 2, \dots, n}$ .

A sort is a decision tree

Fix the number of elements $n$ and fix a comparison sort. We can model its entire behavior as a decision tree: a binary tree whose internal nodes are comparisons and whose leaves are answers.²

Each internal node is labeled $i : j$ , meaning compare $a_{i}$ with $a_{j}$ .
Its two outgoing edges are the two outcomes, $a_{i} \leq a_{j}$ and $a_{i} > a_{j}$ . The algorithm follows the edge matching the actual data.
Each leaf is labeled with a permutation $⟨ π (1), π (2), \dots, π (n) ⟩$ , the sorted order the algorithm declares once it reaches that leaf.

Running the algorithm on a particular input traces a single root-to-leaf path: at each node the data picks the branch, and the leaf reached announces the ordering. The structure of the tree depends only on $n$ , not on the input; the input merely chooses which path through the fixed tree gets walked.

Here is the decision tree for sorting three elements $⟨ a_{1}, a_{2}, a_{3} ⟩$ ; each leaf names the order from smallest to largest.

Decision tree for comparison sorting three elements, with permutation leaves.

Trace the input $⟨ a_{1}, a_{2}, a_{3} ⟩ = ⟨ 6, 2, 9 ⟩$ . At the root we ask $a_{1} : a_{2}$ , that is $6 : 2$ ; since $6 > 2$ we branch right. Next $a_{2} : a_{3}$ , i.e. $2 : 9$ , so $\leq$ sends us left. Finally $a_{1} : a_{3}$ , i.e. $6 : 9$ , again $\leq$ , landing at the leaf $213$ , meaning $a_{2} \leq a_{1} \leq a_{3}$ , which reads off as $2 \leq 6 \leq 9$ . Correct.

Counting leaves and bounding height

Two observations turn this picture into a theorem.

Every permutation needs its own leaf. A correct sort must, for each of the $n!$ possible input orderings, output a different permutation to put it in order. If two distinct input orderings led to the same leaf, that leaf's single fixed output would be wrong for at least one of them. Hence the tree must have at least $n!$ reachable leaves, one per permutation it might be asked to produce.³

Height equals worst-case comparisons. The number of comparisons the algorithm makes on a given input is the length of the root-to-leaf path it walks. The worst-case number of comparisons is therefore the height $h$ of the tree — the longest such path.

Now we connect the two. A binary tree of height $h$ has at most $2^{h}$ leaves (the count at most doubles each level). Combining with the leaf count above,

n! \leq (number of leaves) \leq 2^{h},

and taking $log_{2}$ of both ends gives the key inequality

h \geq log_{2} (n!) .

So every comparison sort, whatever its strategy, must make at least $log_{2} (n!)$ comparisons on its worst input. It remains to see how large that is.

The squeeze. A height-

h

binary tree holds at most

2^{h}

leaves (capacity, doubling per level), while correctness demands at least

n!

leaves (the floor). Forcing

2^{h} \geq n!

gives

h \geq log_{2} (n!)

$log_{2} (n!)$ is $Ω (n log n)$

We need a lower bound on $log_{2} (n!)$ . Stirling's approximation gives the sharp estimate

n! = 2 π n (\frac{n}{e})^{n} (1 + Θ (\frac{1}{n})),

from which, taking logarithms,

log_{2} (n!) = n log_{2} n - n log_{2} e + Θ (log n) = n log_{2} n - Θ (n) .

The leading term is $n log_{2} n$ , so $log_{2} (n!) = Ω (n log n)$ .⁴

If Stirling seems like a heavy tool, an elementary argument reaches the same conclusion. Drop the smallest half of the factors in $n!$ and bound each survivor below by $n /2$ :

n! = n \cdot (n - 1) \dots 2 \cdot 1 \geq n /2 factors \frac{n}{2} \cdot \frac{n}{2} \dots \frac{n}{2} = (\frac{n}{2})^{n /2} .

The picture for $n = 8$ : keep only the larger half of the factors (each at least $n /2 = 4$ ) and throw the rest away. Half the factors, each $\geq n /2$ , already force $n! \geq (n /2)^{n /2}$ .

The elementary bound for

n = 8

. Of the factors

8, 7, \dots, 1

, keep the larger half (top, each

\geq n /2 = 4

) and drop the smaller half (grey); the kept factors alone give

n! \geq (n /2)^{n /2}

Taking $log_{2}$ ,

log_{2} (n!) \geq \frac{n}{2} log_{2} \frac{n}{2} = \frac{n}{2} (log_{2} n - 1) = Ω (n log n) .

Either way the height satisfies $h \geq log_{2} (n!) = Ω (n log n)$ . (For intuition on tightness, mergesort's $Θ (n log n)$ shows the bound is achieved up to constants, so $log_{2} (n!) = Θ (n log n)$ exactly.)

The conclusion

Because comparisons are a lower bound on total work, no comparison-based algorithm can sort $n$ elements in worst-case time $o (n log n)$ . $Heapsort$ and mergesort are therefore asymptotically optimal: they match the lower bound, and no comparison sort can beat them by more than a constant factor.

Two points are worth stressing about what this argument does and does not say.

It is an information-theoretic bound. The algorithm must distinguish $n!$ possible answers, and each comparison is a single yes/no question yielding one bit; $⌈ log_{2} (n!)⌉$ bits are needed to identify one answer among $n!$ . The lower bound counts questions, independent of any cleverness in choosing them.

One comparison, one bit. Each yes/no comparison at best halves the set of still-possible orderings; starting from

n!

candidates, narrowing to a single one takes

\geq ⌈ log_{2} (n!)⌉

comparisons.

It bounds only comparison sorts. The proof leans entirely on the restriction that information arrives one comparison at a time. An algorithm that learns about elements another way, by reading their digits or using them as array indices, sits outside the model, and the $n log n$ floor simply does not apply to it.⁵ The next lesson exploits exactly this loophole to sort in linear time.

Takeaways

A comparison sort learns only the outcomes of element comparisons; this restriction is precisely what makes a lower bound provable.
Any comparison sort is a decision tree: internal nodes are comparisons, leaves are output orderings, and worst-case comparisons equal the tree's height.
Correctness forces $\geq n!$ leaves; a height- $h$ binary tree has $\leq 2^{h}$ leaves, so $h \geq log_{2} (n!)$ .
By Stirling, $log_{2} (n!) = n log_{2} n - Θ (n) = Ω (n log n)$ , so every comparison sort needs $Ω (n log n)$ comparisons in the worst case.
Mergesort and heapsort hit this bound and are thus asymptotically optimal; beating it requires stepping outside the comparison model.

CLRS, §8.1 — Lower Bounds for Sorting — any comparison sort requires $Ω (n log n)$ comparisons in the worst case. ↩
Erickson, Algorithms, Ch. — Lower Bounds via Decision Trees — modeling a comparison sort as a binary decision tree whose internal nodes are comparisons and leaves are output orderings. ↩
CLRS, §8.1 — Lower Bounds for Sorting — a correct sort's decision tree has at least $n!$ reachable leaves, one per permutation. ↩
CLRS, §8.1 — Lower Bounds for Sorting — via Stirling's approximation, $log_{2} (n!) = Ω (n log n)$ , bounding the tree height below. ↩
Erickson, Algorithms, Ch. — Lower Bounds via Decision Trees — the bound holds only for comparison sorts; algorithms reading digits or indices fall outside the model. ↩

The comparison model

A sort is a decision tree

Counting leaves and bounding height

log2​(n!) is Ω(nlogn)

The conclusion

Takeaways

Footnotes

$log_{2} (n!)$ is $Ω (n log n)$