The Comparison Sorting Lower Bound and What It Actually Counts

Sorting by comparing pairs of keys has a floor that no cleverness removes. Any correct algorithm that learns about the input only through questions of the form “is a[i] less than a[j]?” must ask at least $\lceil \log_2 n! \rceil$ such questions in the worst case, which is about $n \log_2 n - 1.44n$ for large $n$. The statement is old, the proof is short, and the interesting part is the fine print: which costs the model ignores, and which kinds of sorting escape it entirely.

Counting the leaves of a decision tree

Fix an input of $n$ distinct keys. A comparison sort’s control flow is determined entirely by the outcomes of the comparisons it performs, so its behaviour on all inputs can be drawn as a binary tree. Each internal node is one comparison of two array positions; the two children are the two possible answers; each leaf is a completed run.

A leaf is only reachable by inputs that produced the same sequence of answers. For the algorithm to be correct, every permutation of the input must end at a leaf whose associated output is that permutation. Two different permutations cannot share a leaf, because the same answer sequence would have to produce two different outputs. So the tree has at least $n!$ leaves.

A binary tree with $L$ leaves has depth at least $\lceil \log_2 L \rceil$, since a tree of depth $d$ holds at most $2^d$ leaves. Therefore the worst-case number of comparisons is at least

$$ \lceil \log_2 n! \rceil $$

For $n = 3$ the tree needs 6 leaves, so depth 3 is the minimum, and 3 comparisons do suffice. For $n = 1000$, $\log_2 1000! \approx 8529$; no comparison sort can beat that on the worst input, and merge sort lands close to it.

Where the linear term comes from

Stirling’s approximation, in the form used for factorials of integers, gives

$$ \log_2 n! = n \log_2 n - n \log_2 e + O(\log n) $$

with $\log_2 e \approx 1.4427$. The linear term is not decoration. At $n = 1000$ it accounts for about 1443 of the 8529 comparisons, roughly seventeen percent of the total. At $n = 10^6$ it is about 1.44 million out of roughly 18.5 million. Any estimate that quotes only $n \log_2 n$ overstates the requirement by that margin, which matters when the estimate is used to predict a merge sort’s comparison count rather than to prove an asymptotic claim.

The same argument gives an average-case version. If the input is drawn uniformly from the $n!$ permutations, the algorithm’s expected number of comparisons satisfies the same inequality, because the entropy of that distribution is $\log_2 n!$. A distribution concentrated on nearly sorted inputs lowers the entropy and with it the bound, which is exactly what an adaptive algorithm such as insertion sort exploits.

An adversary argument that avoids the arithmetic

The decision-tree proof is clean but requires trusting Stirling. An adversary argument reaches the same conclusion with less algebra and generalises more easily.

The adversary maintains a set $S$ of permutations still consistent with every answer given so far, starting with all $n!$ of them. When the algorithm compares positions $i$ and $j$, the adversary partitions $S$ into those permutations where $a[i] < a[j]$ and those where $a[i] > a[j]$. It answers with the larger part, so $|S|$ at least halves. After $k$ comparisons, $|S| \ge n!/2^k$. The algorithm has not finished until $|S| = 1$, because until then two consistent permutations remain and the algorithm cannot know which output is correct. Hence $2^k \ge n!$ and $k \ge \log_2 n!$.

The argument needs one justification: the adversary must be able to answer without committing to a particular permutation. It can, because any two distinct permutations of the same $n$ keys differ in the relative order of at least one pair, so both parts of the partition are nonempty whenever $|S| > 1$ and the answer chosen is realisable by at least one permutation in $S$.

This is also why the bound survives randomisation. A randomised algorithm’s decision tree is a distribution over trees, and every tree in the distribution is subject to the same argument, so the bound holds for each fixed input even when the algorithm’s choices are unpredictable.

What the model refuses to count

The lower bound is a statement about one resource: comparisons between keys. Everything else is free. That is a deliberate idealisation, and three consequences follow.

Moving data is not counted. A sort that performs $n \log n$ comparisons and $n^2$ element moves satisfies the bound and is still slow. Selection sort is the extreme case in the other direction: $\Theta(n^2)$ comparisons but only $n-1$ swaps.

Reading a key is not counted. The model assumes a comparison of two keys costs one unit regardless of how the keys are represented. For fixed-width integers that is accurate. For long strings it is not: comparing two strings of length $m$ can cost $\Theta(m)$, and a sort that compares them $n \log n$ times can be dominated by the comparison cost rather than the comparison count. This is the reason comparator contracts matter as much as comparison counts.

The keys’ structure is not counted. If keys are $w$-bit integers, the algorithm may look at the bits instead of asking comparison questions; the number of comparisons it then performs is zero, not reduced. Radix and counting sorts do exactly that and sort in a fixed number of passes, each $\Theta(n)$, with no comparisons at all. The lower bound does not forbid this because the bound’s model forbids the technique, not because the sort has found a loophole.

Duplicate keys change the leaf count

The $n!$ figure assumes distinct keys. With multiplicities $m_1, m_2, \ldots, m_r$ summing to $n$, the number of distinguishable outputs is the multinomial

$$ \frac{n!}{m_1! , m_2! \cdots m_r!} $$

and the bound becomes the base-2 logarithm of that number. Three cases show the range. All keys distinct: the full $\log_2 n!$. Two values, each repeated $n/2$ times: about $n$ bits, so a linear number of comparisons suffices. All keys equal: the multiset has one arrangement, the bound is zero, and a correct algorithm needs no comparisons at all, only the $\Theta(n)$ work of examining the input to discover that fact.

This is why partitioning schemes that separate keys into less-than, equal, and greater-than groups beat schemes with two outcomes on inputs with many repeats; the three-way partition turns a quadratic case into a linear one, and the multiset bound is the reason.

What the bound implies for choosing an algorithm

Algorithm	Worst-case comparisons	Stable	Extra space
Insertion sort	$\Theta(n^2)$	yes	$O(1)$
Merge sort	$\Theta(n \log n)$	yes	$\Theta(n)$
Heapsort	$\Theta(n \log n)$	no	$O(1)$
Quicksort	$\Theta(n^2)$	no	$O(\log n)$ stack
LSD radix	no key comparisons	yes	$\Theta(n + 2^r)$

The bound says nothing about which of the $\Theta(n \log n)$ algorithms to use. Merge sort’s comparison count is close to the floor and its stability is free; quicksort’s count is larger in the worst case but its inner loop is a single compare and increment; heapsort buys the worst-case bound with poor locality of access. Those differences are constants and memory behaviour, not asymptotics, and they are where real choices are made.

A comparison sort that meets the bound on every input exists. Several do, at different costs along different axes. Merge sort is within a small constant of the floor and is stable, at the price of a secondary buffer. Its in-place alternative, heapsort, reaches the same worst-case bound with constant space, but the heap’s sift-down jumps between distant indices, so heapsort’s constant is larger once the array outgrows cache. The practical engineering question below the bound is therefore not “can we reach it” but “which constant and which memory budget can we live with”. Choosing between those constants under an additional worst-case constraint is where the analysis in introsort picks up.

The one thing the bound does rule out is a comparison sort with a better worst-case comparison count. No amount of engineering produces one, because the argument is combinatorial rather than algorithmic: it constrains the shape of any correct decision procedure, not the skill of its author.