---
title: Lower Bounds for Comparison Sorting
module: Sorting & Order Statistics
moduleNumber: 3
lessonNumber: 2
order: 302
summary: |
  Every sort we have seen runs in $\Omega(n\log n)$, and that is no accident.
  Modeling a sort as a decision tree of comparisons, we show any such tree must
  have $n!$ leaves, forcing height $\ge \log_2(n!) = \Omega(n\log n)$ — a bound
  no comparison sort beats in the worst case, on average, or with randomness.
topics: [Comparison Sorting]
sources:
  - book: CLRS
    ref: "§8.1 — Lower Bounds for Sorting"
  - book: Erickson
    ref: "Ch. — Lower Bounds via Decision Trees"
practice:
  - title: 'Guess Number Higher or Lower'
    slug: guess-number-higher-or-lower
    difficulty: Easy
  - title: 'Find the Duplicate Number'
    slug: find-the-duplicate-number
    difficulty: Medium
  - title: 'Maximum Gap'
    slug: maximum-gap
    difficulty: Hard
---

[Mergesort](/algorithms/divide-and-conquer/mergesort),
[heapsort](/algorithms/sorting/heaps-and-heapsort), and (in expectation)
[quicksort](/algorithms/divide-and-conquer/quicksort) all run in
$\Theta(n\log n)$. Insertion sort and the rest do worse. None does _better_.
Could some cleverer algorithm beat $n\log n$? The 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 $\Omega(n\log n)$ comparisons in the worst case.[^clrs-lb]
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 \le a_j$?" (or $<$, $\ge$, $>$, $=$). 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 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 $\set{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.[^erickson-dt]

- Each **internal node** is labeled $i : j$, meaning "compare $a_i$ with $a_j$."
- Its two **outgoing edges** are the two outcomes, $a_i \le a_j$ and
  $a_i > a_j$. The algorithm follows the edge matching the actual data.
- Each **leaf** is labeled with a permutation
  $\vector{\pi(1), \pi(2), \dots, \pi(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 $\vector{a_1, a_2, a_3}$;
each leaf names the order from smallest to largest.

$$
% caption: Decision tree for comparison sorting three elements, with permutation leaves.
\begin{tikzpicture}[level distance=13mm,
  level 1/.style={sibling distance=46mm},
  level 2/.style={sibling distance=23mm},
  level 3/.style={sibling distance=15mm},
  inner/.style={draw, circle, minimum size=8mm, font=\small},
  leaf/.style={draw, minimum size=6mm, font=\scriptsize},
  every edge/.append style={font=\scriptsize},
  el/.style={fill=white, inner sep=1.5pt}]
  \node[inner] {$1\!:\!2$}
    child {node[inner] {$2\!:\!3$}
      child {node[leaf] {$123$}
        edge from parent node[left,el] {$\le$}}
      child {node[inner] {$1\!:\!3$}
        child {node[leaf] {$132$} edge from parent node[left,el] {$\le$}}
        child {node[leaf] {$312$} edge from parent node[right,el] {$>$}}
        edge from parent node[right,el] {$>$}}
      edge from parent node[left,el] {$\le$}}
    child {node[inner] {$2\!:\!3$}
      child {node[inner] {$1\!:\!3$}
        child {node[leaf] {$213$} edge from parent node[left,el] {$\le$}}
        child {node[leaf] {$231$} edge from parent node[right,el] {$>$}}
        edge from parent node[left,el] {$\le$}}
      child {node[leaf] {$321$}
        edge from parent node[right,el] {$>$}}
      edge from parent node[right,el] {$>$}};
\end{tikzpicture}
$$

Trace the input $\vector{a_1,a_2,a_3} = \vector{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 $\le$ sends us left. Finally $a_1 : a_3$, i.e. $6 : 9$, again
$\le$, landing at the leaf $213$, meaning $a_2 \le a_1 \le a_3$, which reads off
as $2 \le 6 \le 9$. Correct.

$$
% caption: The path the input $\langle 6,2,9\rangle$ walks through the tree. Each
%          comparison's outcome (annotated with the concrete values) picks one branch;
%          the untaken subtrees (grey) are never touched. Three comparisons, one leaf.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  cmp/.style={circle, draw, thick, minimum size=9mm, inner sep=0pt, font=\small},
  lf/.style={draw, thick, minimum height=6.5mm, inner sep=3pt, font=\small},
  gcmp/.style={circle, draw=black, minimum size=9mm, inner sep=0pt, font=\small, text=black},
  glf/.style={draw=black, minimum height=6.5mm, inner sep=3pt, font=\small, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cmp, draw=acc] (a) at (0,0) {$1\!:\!2$};
  \node[gcmp] (gl) at (-2.4,-1.4) {$2\!:\!3$};
  \node[cmp, draw=acc] (b) at (2.4,-1.4) {$2\!:\!3$};
  \node[cmp, draw=acc] (c) at (1.2,-2.8) {$1\!:\!3$};
  \node[glf] (gr) at (3.8,-2.8) {321};
  \node[lf, draw=acc, fill=acc!10] (d) at (0.2,-4.2) {213};
  \node[glf] (gd) at (2.4,-4.2) {231};
  \draw[black] (a)--(gl);
  \draw[acc, thick] (a)--(b);
  \draw[acc, thick] (b)--(c);
  \draw[black] (b)--(gr);
  \draw[acc, thick] (c)--(d);
  \draw[black] (c)--(gd);
  \node[text=acc, anchor=west] at (1.55,-0.55) {6 $>$ 2};
  \node[text=acc, anchor=east] at (1.55,-2.15) {2 $\le$ 9};
  \node[text=acc, anchor=east] at (0.45,-3.55) {6 $\le$ 9};
  \node[text=black, anchor=east] at (-3.25,-1.4) {never visited};
\end{tikzpicture}
$$

Notice what the tree does _not_ record: the values themselves. The inputs
$\vector{6,2,9}$, $\vector{5,1,8}$, and $\vector{200,-3,417}$ all walk the same
path, because they present the same pattern of comparison outcomes. The tree
partitions all possible inputs into finitely many equivalence classes, one per
leaf, and that finiteness is what we now exploit.

::impl{algo="comparison_decision_tree"}

## Counting leaves and bounding height

Two observations turn this picture into a theorem.

> **Claim (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.[^clrs-leaves]

The contrapositive is worth seeing concretely. Suppose the inputs
$\vector{1,2,3}$ and $\vector{2,1,3}$ both ended at a leaf labeled $123$, i.e.
"declare $a_1 \le a_2 \le a_3$." For the first input that is right. For the
second it asserts $2 \le 1$, which is false: the algorithm has mis-sorted. A leaf
commits to one answer, so each of the $n!$ answers the adversary might require
needs a leaf of its own.

$$
% caption: Why leaves cannot be shared. If both inputs reached the leaf that declares
%          $a_1 \le a_2 \le a_3$, the verdict would be correct for $\langle 1,2,3\rangle$
%          but would assert $2 \le 1$ for $\langle 2,1,3\rangle$ — a wrong output.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  arr/.style={draw, minimum height=6.5mm, inner sep=4pt, font=\small},
  lf/.style={draw, thick, minimum height=7mm, inner sep=4pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[arr] (i1) at (0,1.0) {input 1, 2, 3};
  \node[arr] (i2) at (0,-1.0) {input 2, 1, 3};
  \node[lf, draw=acc, fill=acc!10] (leaf) at (4.6,0) {leaf 123: declare a1 $\le$ a2 $\le$ a3};
  \draw[->, acc, thick] (i1.east) to[out=0, in=160] (leaf.west);
  \draw[->, acc, thick] (i2.east) to[out=0, in=200] (leaf.west);
  \node[text=black, anchor=west] at (8.0,1.0) {correct for input 1};
  \node[text=red!75!black, anchor=west] (bad) at (8.0,-1.0) {wrong: says 2 $\le$ 1};
  \draw[black, ->] (leaf.north) to[out=60, in=185] (7.9,1.0);
  \draw[red!75!black, ->] (leaf.south) to[out=-60, in=175] (bad.west);
\end{tikzpicture}
$$

> **Claim (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! \;\le\; (\text{number of leaves}) \;\le\; 2^{h},
$$

and taking $\log_2$ of both ends gives the key inequality

$$
h \;\ge\; \log_2(n!).
$$

So _every_ comparison sort, whatever its strategy, must make at least
$\log_2(n!)$ comparisons on its worst input.

Check it against the tree we drew. For $n = 3$ there are $3! = 6$ orderings, and
$\log_2 6 \approx 2.58$, so the height must be at least $\lceil 2.58\rceil = 3$.
Two comparisons cannot suffice: a tree of height $2$ has at most $2^2 = 4$
leaves, and $4 < 6$. Our tree has height exactly $3$, so for three elements it
is _optimal_: no comparison sort does better, and the bound is met with
equality. It remains to see how large $\log_2(n!)$ grows in general.

$$
% caption: 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 \ge n!$ gives $h \ge \log_2(n!)$.
\begin{tikzpicture}[
  nd/.style={circle, draw, minimum size=5mm, inner sep=0pt},
  lf/.style={draw, fill=acc!16, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[nd] (a) at (0,0) {};
  \node[nd] (b1) at (-1.6,-1.0) {};
  \node[nd] (b2) at (1.6,-1.0) {};
  \node[nd] (c1) at (-2.4,-2.0) {};
  \node[nd] (c2) at (-0.8,-2.0) {};
  \node[nd] (c3) at (0.8,-2.0) {};
  \node[nd] (c4) at (2.4,-2.0) {};
  \draw (a)--(b1); \draw (a)--(b2);
  \draw (b1)--(c1); \draw (b1)--(c2); \draw (b2)--(c3); \draw (b2)--(c4);
  \foreach \cx in {-2.4,-0.8,0.8,2.4} {
    \node[lf] at (\cx-0.3,-3.0) {};
    \node[lf] at (\cx+0.3,-3.0) {};
    \draw (\cx,-2.0)--(\cx-0.3,-3.0);
    \draw (\cx,-2.0)--(\cx+0.3,-3.0);
  }
  \node[font=\scriptsize, anchor=west] at (3.1,0) {$2^0=1$};
  \node[font=\scriptsize, anchor=west] at (3.1,-1.0) {$2^1=2$};
  \node[font=\scriptsize, anchor=west] at (3.1,-2.0) {$2^2=4$};
  \node[font=\scriptsize, anchor=west, text=acc] at (3.1,-3.0) {at most $2^h$ leaves};
  \node[font=\footnotesize, text=red!70!black] at (0,-3.95) {correctness demands n! leaves, so $2^h \ge n!$ and $h \ge \log_2(n!)$};
\end{tikzpicture}
$$

::impl{algo="sorting_lower_bound#min_comparisons"}

## $\log_2(n!)$ is $\Omega(n\log n)$

We need a lower bound on $\log_2(n!)$.
[**Stirling's approximation**](/algorithms/foundations/asymptotic-analysis) gives
the sharp estimate

$$
n! = \sqrt{2\pi n}\parens{\frac{n}{e}}^{n}\!\parens{1 + \Theta\!\parens{\tfrac{1}{n}}},
$$

from which, taking logarithms,

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

The leading term is $n\log_2 n$, so $\log_2(n!) = \Omega(n\log n)$.[^clrs-stirling]

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)\cdots 2\cdot 1 \;\ge\; \underbrace{\frac{n}{2}\cdot\frac{n}{2}\cdots\frac{n}{2}}_{n/2 \text{ factors}} \;=\; \parens{\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 $\ge n/2$, already force
$n!\ge (n/2)^{n/2}$.

$$
% caption: The elementary bound for $n=8$. Of the factors $8,7,\dots,1$, keep the larger
%          half (top, each $\ge n/2=4$) and drop the smaller half (grey); the kept factors
%          alone give $n! \ge (n/2)^{n/2}$.
\begin{tikzpicture}[
  keep/.style={draw, fill=acc!15, minimum size=7mm, font=\small, inner sep=0pt},
  drop/.style={draw, fill=black!8, minimum size=7mm, font=\small, text=black, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \v/\i in {8/0,7/1,6/2,5/3} \node[keep] at (\i*0.8,0) {\v};
  \foreach \v/\i in {4/4,3/5,2/6,1/7} \node[drop] at (\i*0.8,0) {\v};
  % kept group: thick accent rule with end ticks, above
  \draw[acc, thick] (-0.35,0.5) -- (2.75,0.5);
  \draw[acc, thick] (-0.35,0.42) -- (-0.35,0.5);
  \draw[acc, thick] (2.75,0.42) -- (2.75,0.5);
  \node[font=\scriptsize, text=acc, anchor=south] at (1.2,0.56) {kept: 4 factors, each at least 4};
  % dropped group: grey rule with end ticks, below
  \draw[black, thick] (2.85,-0.5) -- (5.95,-0.5);
  \draw[black, thick] (2.85,-0.42) -- (2.85,-0.5);
  \draw[black, thick] (5.95,-0.42) -- (5.95,-0.5);
  \node[font=\scriptsize, text=black, anchor=north] at (4.4,-0.56) {dropp\/ed};
  \node[font=\footnotesize, text=acc, anchor=west] at (6.5,0) {pro\/duct $\ge 4^4 = 256$};
\end{tikzpicture}
$$

Taking $\log_2$,

$$
\log_2(n!) \;\ge\; \frac{n}{2}\log_2\frac{n}{2} \;=\; \frac{n}{2}\parens{\log_2 n - 1} \;=\; \Omega(n\log n).
$$

Either way the height satisfies $h \ge \log_2(n!) = \Omega(n\log n)$. (For
intuition on tightness, mergesort's $\Theta(n\log n)$ shows the bound is achieved
up to constants, so $\log_2(n!) = \Theta(n\log n)$ exactly.)

### How tight is it, concretely?

The bound $\lceil\log_2(n!)\rceil$ is not just asymptotically right; for small
$n$ it is close to what real algorithms achieve. Mergesort's worst-case
comparison count obeys $W(n) = W(\floor{n/2}) + W(\ceil{n/2}) + n - 1$ with
$W(1)=0$, and lining it up against the bound:

| $n$ | $n!$ | $\lceil\log_2(n!)\rceil$ | mergesort worst case $W(n)$ |
| --- | --- | --- | --- |
| $3$ | $6$ | $3$ | $3$ |
| $4$ | $24$ | $5$ | $5$ |
| $5$ | $120$ | $7$ | $8$ |
| $8$ | $40{,}320$ | $16$ | $17$ |
| $16$ | $\approx 2.09 \times 10^{13}$ | $45$ | $49$ |

For $n = 3$ and $n = 4$ mergesort meets the information bound exactly. From
$n = 5$ a gap opens: the bound says $7$, mergesort spends $8$. The bound is a
_floor_: it guarantees no algorithm goes below it but does not
promise an algorithm achieving it, and for most $n$ the best known sorting
procedures sit slightly above $\lceil\log_2(n!)\rceil$. Asymptotically the gap
is only $\Theta(n)$ out of $\Theta(n \log n)$, which is why mergesort and
heapsort count as optimal.

::impl{algo="sorting_lower_bound#log2_factorial+stirling_log2_factorial+elementary_lower_bound"}

## The bound survives averaging and randomness

A worst-case bound leaves two possible outs: an algorithm slow on a
few pathological inputs but fast _on average_, or a randomized algorithm, as
with [quicksort](/algorithms/divide-and-conquer/quicksort). Neither
helps here: the $\Omega(n\log n)$ bound holds for the _average_ input
and for randomized algorithms too.[^clrs-avg]

> **Theorem (Average-case lower bound).** Any deterministic comparison sort
> makes at least $\log_2(n!)$ comparisons _on average_ over the $n!$ equally
> likely input orderings.

> **Proof.** Each of the $n!$ input orderings reaches its own leaf, so the
> average number of comparisons is the average depth of $n!$ distinct leaves
> $\ell_1, \dots, \ell_{n!}$ with depths $d_1, \dots, d_{n!}$. In any binary
> tree the leaf depths satisfy the Kraft inequality
> $\sum_{i} 2^{-d_i} \le 1$: a leaf at depth $d$ occupies a $2^{-d}$ fraction of
> the tree's address space, and disjoint leaves cannot overcommit it. The
> function $x \mapsto 2^{-x}$ is convex, so by Jensen's inequality
>
> $$
> 2^{-\bar d} \;\le\; \frac{1}{n!}\sum_{i} 2^{-d_i} \;\le\; \frac{1}{n!},
> \qquad \text{where } \bar d = \frac{1}{n!}\sum_i d_i .
> $$
>
> Taking $\log_2$ gives $\bar d \ge \log_2(n!)$. $\qed$

The worst case bounded the _deepest_ leaf; this bounds the _average_ leaf, and
the answer is the same $\Omega(n\log n)$. Intuitively, a binary tree that must
reach $n!$ distinct leaves cannot make more than a vanishing fraction of them
shallow: balancing the tree perfectly is the best possible arrangement, and even
then every leaf sits at depth about $\log_2(n!)$.

$$
% caption: Average depth is minimized by balance. Both trees have $4$ leaves; the balanced
%          tree (left) has every leaf at depth $2$, average $2$, while the lopsided tree
%          (right) averages $(1+2+3+3)/4 = 2.25$. No shape with $L$ leaves beats average
%          depth $\log_2 L$.
\begin{tikzpicture}[font=\footnotesize,
  nd/.style={circle, draw, minimum size=4.5mm, inner sep=0pt},
  lf/.style={draw, fill=acc!16, minimum size=4.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % balanced
  \node[nd] (a) at (0,0) {};
  \node[nd] (b1) at (-1.0,-1.0) {};
  \node[nd] (b2) at (1.0,-1.0) {};
  \node[lf] (c1) at (-1.5,-2.0) {};
  \node[lf] (c2) at (-0.5,-2.0) {};
  \node[lf] (c3) at (0.5,-2.0) {};
  \node[lf] (c4) at (1.5,-2.0) {};
  \draw (a)--(b1); \draw (a)--(b2);
  \draw (b1)--(c1); \draw (b1)--(c2); \draw (b2)--(c3); \draw (b2)--(c4);
  \node[text=acc] at (0,-2.8) {depths 2, 2, 2, 2: average 2};
  % lopsided
  \node[nd] (x) at (6.0,0) {};
  \node[lf] (y1) at (5.0,-1.0) {};
  \node[nd] (y2) at (7.0,-1.0) {};
  \node[lf] (z1) at (6.4,-2.0) {};
  \node[nd] (z2) at (7.6,-2.0) {};
  \node[lf] (w1) at (7.0,-3.0) {};
  \node[lf] (w2) at (8.2,-3.0) {};
  \draw (x)--(y1); \draw (x)--(y2);
  \draw (y2)--(z1); \draw (y2)--(z2);
  \draw (z2)--(w1); \draw (z2)--(w2);
  \node[text=black] at (6.6,-3.8) {depths 1, 2, 3, 3: average 2.25};
\end{tikzpicture}
$$

Randomization fares no better. A randomized comparison sort is a probability
distribution over deterministic decision trees, one tree per possible sequence
of coin flips. Feed it a uniformly random permutation: whichever tree the coins
select, that tree's expected comparison count on random input is at least
$\log_2(n!)$ by the theorem above, so the expectation over both coins and input
is also at least $\log_2(n!)$. There must then exist a _fixed_ input on which
the randomized algorithm's expected count is $\ge \log_2(n!)$. Coin flips can
smooth out which inputs are bad, as they do for quicksort's pivots, but they
do not change the number of comparisons required.[^clrs-avg]

## The conclusion

> **Theorem.** Any comparison sort makes $\Omega(n\log n)$ comparisons in the
> worst case.

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)$. $\textsc{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 boundaries mark off 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; $\lceil \log_2(n!)\rceil$ bits are needed to identify one
  answer among $n!$. The lower bound counts questions, independent of any
  cleverness in choosing them.

$$
% caption: 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 $\ge \lceil\log_2(n!)\rceil$ comparisons.
\begin{tikzpicture}[
  box/.style={draw, minimum height=6mm, font=\small, inner sep=3pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=acc!20, minimum width=42mm] (s0) at (0,0) {$n!$ possible orderings};
  \node[box, fill=acc!15, minimum width=30mm] (s1) at (-0.9,-1.05) {half at best: n!/2};
  \node[box, fill=acc!11, minimum width=20mm] (s2) at (-1.6,-2.1) {n!/4};
  \node[box, fill=acc!8, minimum width=12mm] (s3) at (-2.1,-3.15) {...};
  \node[box, fill=acc!22, draw=acc, minimum width=10mm] (s4) at (-2.4,-4.2) {$1$};
  \draw[->, >=Stealth] (s0.south) to[bend right=12] node[right, font=\scriptsize] {compare} (s1.north);
  \draw[->, >=Stealth] (s1.south) to[bend right=12] node[right, font=\scriptsize] {compare} (s2.north);
  \draw[->, >=Stealth] (s2.south) to[bend right=12] (s3.north);
  \draw[->, >=Stealth] (s3.south) to[bend right=12] (s4.north);
  \node[font=\footnotesize, anchor=west, text=acc] at (1.7,-2.1) {at least $\log_2(n!)$ steps};
\end{tikzpicture}
$$
- 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.[^erickson-model] The next lesson exploits exactly this
  loophole to sort in
  [**linear time**](/algorithms/sorting/linear-time-sorting).

> **Remark (The same trick bounds other problems).** Decision trees are a
> general-purpose lower-bound tool, not a sorting special. Searching a sorted
> array of $n$ elements by comparisons must distinguish $n + 1$ outcomes (the
> $n$ positions plus "absent"), so its decision tree needs $n+1$ leaves and
> height $\ge \log_2(n+1)$ — binary search is optimal for the same reason
> mergesort is.[^erickson-model] Whenever a
> problem has $K$ distinguishable answers and each probe yields one bit,
> $\lceil\log_2 K\rceil$ probes are forced.

## Other lower-bound techniques

The leaf-counting argument is one member of a larger family of lower-bound
techniques. Three directions are worth knowing, because they show both how far
the idea reaches and where it stops.

**Adversary arguments.** Counting leaves bounds the _tree_; an **adversary
argument** bounds an algorithm directly by playing the role of a malicious input
that answers each comparison in whichever way keeps the most work ahead. The
adversary never commits to a fixed permutation — it only promises to stay
consistent with every answer it has given — and it steers the algorithm down a
long path. This reproves $\Omega(n\log n)$ for sorting and, more sharply, pins
exact constants the leaf bound cannot see. The classic result is that finding
_both_ the minimum and maximum of $n$ elements needs exactly
$\lceil 3n/2\rceil - 2$ comparisons: an adversary that tracks how many elements
have "lost" and "won" so far forces any algorithm to spend that many and no
fewer. Leaf-counting gives the right growth rate; the adversary gives the right
constant.

**Sorting networks and the 0-1 principle.** A **sorting network** is an
oblivious sort: a fixed sequence of compare-exchange operations on wire pairs,
chosen in advance with no data-dependent branching, so the same comparisons run
regardless of input. That obliviousness suits hardware and SIMD
lanes. Proving a network correct on _all_ $n!$ inputs directly is infeasible; the
**0-1 principle** reduces it: a comparison network sorts every input if and
only if it sorts every input of $0$s and $1$s (Knuth). Since a comparator's
behavior depends only on the _relative_ order of its two inputs, correctness on
the $2^n$ binary inputs — far fewer than $n!$, and checkable one threshold at a
time — implies correctness on all inputs. Batcher's bitonic network sorts in
$\Theta(n\log^2 n)$ comparisons across $\Theta(\log^2 n)$ parallel depth, and the
0-1 principle is what makes verifying it tractable.

$$
% caption: The 0-1 principle. A comparison network's behavior on any input is fixed by the
%          relative order of the compared pairs, so if it sorts all $2^n$ binary inputs
%          (bottom, checkable one threshold at a time) it sorts all $n!$ inputs (top).
\begin{tikzpicture}[font=\footnotesize, >=Stealth,
  box/.style={draw, minimum height=7mm, inner sep=4pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=black!5, minimum width=34mm] (all) at (0,0) {sorts all $n!$ inputs};
  \node[box, fill=acc!15, draw=acc, minimum width=42mm] (zo) at (0,-1.5) {sorts all $2^n$ binary inputs};
  \draw[->, acc, thick] (zo.north) -- node[right, font=\scriptsize] {0-1 principle} (all.south);
  \node[font=\scriptsize, text=black, anchor=west] at (2.6,-1.5) {far fewer, easy to check};
\end{tikzpicture}
$$

**Beyond comparisons: the algebraic model.** The comparison model is not the only
one with provable floors. In the **algebraic decision tree** model, where each
node tests the sign of a polynomial in the inputs, one can prove that **element
distinctness** — deciding whether $n$ reals are all different — needs
$\Omega(n\log n)$ operations (Ben-Or, 1983). This matters because it transfers:
many geometry problems, such as deciding whether any two of $n$ points coincide
or computing a convex hull, contain element distinctness as a sub-question and so
inherit the $\Omega(n\log n)$ bound. The lesson is that lower bounds are always
_relative to a model_: enlarge the model (comparisons to indexing, as the [next
lesson](/algorithms/sorting/linear-time-sorting) does; or comparisons to algebraic
tests) and the floor can move. What the decision-tree argument proves is not that
sorting is hard in an absolute sense, but that it is hard for algorithms limited
to the questions the model allows.[^erickson-model]

## Takeaways

- A **comparison sort** learns only the outcomes of element comparisons; this
  restriction is 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 **$\ge n!$ leaves**; a height-$h$ binary tree has $\le 2^h$
  leaves, so $h \ge \log_2(n!)$.
- By Stirling, $\log_2(n!) = n\log_2 n - \Theta(n) = \Omega(n\log n)$, so
  **every comparison sort needs $\Omega(n\log n)$ comparisons** in the worst
  case.
- The floor survives both escape hatches: by Kraft + Jensen the **average**
  input also costs $\ge \log_2(n!)$, and a **randomized** sort is just a
  distribution over decision trees, so coin flips do not help either.
- Mergesort and heapsort hit this bound and are thus **asymptotically optimal**;
  beating it requires stepping _outside_ the comparison model.
- The idea generalizes: **adversary arguments** pin exact constants (min-and-max
  in $\lceil 3n/2\rceil - 2$), the **0-1 principle** reduces verifying a sorting
  network to its $2^n$ binary inputs, and **algebraic decision trees** carry an
  $\Omega(n\log n)$ floor to element distinctness and the geometry problems built
  on it. Every lower bound is relative to its model.

[^clrs-lb]: **CLRS**, §8.1 — Lower Bounds for Sorting — any comparison sort requires $\Omega(n\log n)$ comparisons in the worst case.
[^erickson-dt]: **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-leaves]: **CLRS**, §8.1 — Lower Bounds for Sorting — a correct sort's decision tree has at least $n!$ reachable leaves, one per permutation.
[^clrs-stirling]: **CLRS**, §8.1 — Lower Bounds for Sorting — via Stirling's approximation, $\log_2(n!) = \Omega(n\log n)$, bounding the tree height below.
[^clrs-avg]: **CLRS**, Problem 8-1 — Probabilistic lower bounds on comparison sorting. The average-case bound over uniformly random permutations, and its extension to randomized comparison sorts as distributions over deterministic decision trees.
[^erickson-model]: **Erickson**, _Algorithms_, Ch. — Lower Bounds via Decision Trees — the bound holds only for comparison sorts; algorithms reading digits or indices fall outside the model.