Motivation
Merge sort and heap sort use comparisons in the worst case. Is that cost an accident of those algorithms, or is there an obstacle shared by all comparison-based sorting methods? A decision tree turns an algorithm's possible comparison outcomes into a counting problem: enough different outcomes must exist to distinguish the possible input orders.
The model matters. Counting sort can run in linear time when keys lie in a suitably small integer range because it uses key values to index an array. It is not a counterexample to a lower bound that assumes comparisons are the only way to obtain information about key order.
Definitions
Definition 1.8.1
(Deterministic comparison sorting algorithm)
A deterministic comparison sorting algorithm receives distinct keys and must output those keys in increasing order for every input ordering. Its control flow may depend on the results of pairwise key comparisons. We count key comparisons, not moves or arithmetic unrelated to key values. For distinct keys, a comparison has two possible outcomes: less than or greater than.
Definition 1.8.2
(Decision tree of a comparison sort)
A comparison decision tree has one internal node for each possible comparison at that point of the algorithm, with one outgoing edge for each outcome. A leaf records the output ordering chosen after the observed outcomes. Different branches may have different lengths; the maximum root-to-leaf length is the worst-case number of comparisons.
Theorems
Theorem 1.8.3
(Comparison sorting requires many comparisons)
Every deterministic comparison sort on distinct keys has a worst-case input requiring at least comparisons. Consequently its worst-case comparison count is .
Theorem 1.8.4
(Counting sort for bounded integer keys)
For integer keys in with , counting sort can produce a stable sorted output in time and auxiliary space in the array-indexing model described below.
Proof: counting leaves
Proof
(Counting the leaves of the decision tree)
There are possible relative orders of distinct input positions. A correct comparison algorithm must distinguish all of them. If two different relative orders reached the same leaf, the algorithm would output the same permutation of input positions for both. At least one of those outputs would be incorrect, because the correct increasing order of positions differs.
A binary tree of height has at most leaves. This remains true when some leaves occur before depth : extend each short path conceptually to depth , or prove the bound by induction. Therefore a decision tree correct on all orders must satisfy , giving .
For an elementary asymptotic bound, when at least factors in are at least . Thus , and its base-two logarithm is . The upper bound follows because each factor is at most . Hence the information requirement is of order .
Proof X-ray
Why two orders cannot share a leaf
The proof has three links. First, a leaf fixes one output permutation, because the algorithm has seen only the comparison outcomes on the path to it. Second, the keys are distinct, so different relative orders require different output permutations; this is where distinctness is used. Hence at least distinct leaves exist. Third, the step that turns a count into a time bound is : a binary tree cannot have more leaves than , so a large number of leaves forces a large height.
Each link can be checked by asking what fails without it. If the algorithm could read key values directly (not only compare them), a leaf would not be determined by a path of binary outcomes, and the leaf count would no longer limit the running time. If equal keys were allowed, fewer than outputs would be needed. The proof does not say where the deep leaf lies, only that one exists.
Counting sort and stability
Definition 1.8.5
(Stable sorting)
A sorting algorithm is stable if records with equal keys appear in the output in the same relative order as in the input.
For each key value , count how many input items have that value. Compute prefix totals , the number of items with key at most . Scan the input from right to left. For an item with key , place it in output position using zero-based indexing, then decrement .
Proof
(Counting sort is correct, stable and costs )
The positions reserved for key are precisely the contiguous block after all positions for smaller keys and before all positions for larger keys. Each item consumes one unused position in that block, so the output is sorted and every input item appears once. Scanning from right to left fills the block from right to left: if two equal-key items occur in a given order in the input, the later item is placed in a later output position. Their relative order is preserved, which is stability.
Initializing counts and computing prefix totals cost ; counting and output placement cost . The count array uses space and the output array uses . Indexing by a key is assumed constant time, and keys are promised to be integers in the stated range. The range size is part of the cost: if it is very large relative to , this algorithm need not be faster or more space-efficient than comparison sorting.
Worked examples
Worked example 1.8.6
(Three distinct keys)
There are possible orders. A binary comparison tree of height two has at most four leaves, so some input needs at least comparisons. Three comparisons always suffice, for example by comparing two keys and inserting the third into their sorted pair.
Worked example 1.8.7
(Counting a small array)
For keys with , the counts for values are . Prefix totals are . They reserve output positions for key zero, for key one, and for key two. The output keys are .
Worked example 1.8.8
(Equal keys retain their order)
Suppose the two key-two items above are labeled and in their input order. Scanning from right to left places in position three first and in position two later. Their output order is , so their associated records remain stable.
Worked example 1.8.9
(A large range changes the tradeoff)
With and keys promised in a range of size , a count array would require a billion entries. The bound is correct, but its term dominates. A comparison sort can avoid allocating one counter per possible key value.
Common mistakes
Counterexample mode
A linear-time integer sort does not refute the tree bound
A tempting claim is that every sorting algorithm needs steps. Counting sort refutes it for small key ranges. Take keys in , so . Counting sort runs in steps, whereas , so a comparison sort needs at least comparisons on some input. No contradiction arises, because the decision-tree proof counts only binary comparisons of keys, while counting sort reads each integer key as an array index, an operation that distinguishes among values in one step. It obtains information outside the comparison-only model, so the lower-bound hypotheses do not apply. The correct claim is the restricted one: comparisons for sorting arbitrary distinct keys by comparisons alone.
Common mistake
(A worst-case bound is not a bound for every input)
A lower bound on worst-case comparisons does not say every input needs that many comparisons. An adaptive algorithm may quickly recognize some already ordered inputs while still requiring many comparisons on another input. It also does not count the time spent moving large records or allocating memory.
Common mistake
(The count presumes distinct keys)
The lower bound uses distinct keys to guarantee different required relative orders. Equal keys can reduce the number of distinguishable orders, and stability imposes its own requirement on equal-key records. The hard family of distinct inputs is enough to establish the worst-case lower bound for an algorithm that must handle all inputs.
What the model reveals
The decision tree abstracts away the specific comparisons selected by the algorithm. One algorithm may compare neighboring keys, another may compare widely separated keys, and their trees can have very different shapes. The leaf count constrains all of them at once because each binary outcome can at most double the number of distinguishable branches.
The proof does not require the tree to be balanced. A very short leaf for one input leaves fewer short paths available for the many other orders. The height bound says that at least one path is long; it does not identify which input realizes that path for a particular algorithm.
For bounded integer keys, the model provides more than comparisons. A key value directly selects one of counters, and the algorithm pays for initializing and traversing those counters. The two analyses can coexist: one proves a limitation under restricted access to keys, while the other exploits a stronger operation and accounts for its memory range.
Concept lensAnalytic
The same bound with its constants
Stirling's formula gives
so the information bound is , not merely . For the right side is about , matching the value used above.
Average depth and randomized algorithms
The same counting idea also bounds the average number of comparisons over a uniformly random input order. Let the possible orders end at leaf depths . For any binary tree, the leaf weights satisfy . One proof assigns weight one to the root and splits each node's weight equally between its children; the weights of all leaves sum to at most the initial weight.
The arithmetic–geometric mean inequality gives
Taking base-two logarithms and rearranging yields . Thus even the average over uniformly chosen distinct-key orders requires at least comparisons for every deterministic comparison sort. This is a stronger statement than merely saying one path has that length.
Now consider a randomized comparison sort that is correct for every input and every random choice and has fixed finite bounds on both comparisons and random bits. Fix its random bits: the resulting deterministic comparison tree still sorts every input order. Its average depth under the uniform input distribution is at least . Averaging over the random bits preserves this inequality. Therefore at least one fixed input order has expected comparison count at least , where the remaining expectation is over the algorithm's own random choices. This argument does not claim that every input has that expected cost.
The fixed finite bounds on comparisons and random bits make all averages ordinary finite sums. More general almost-surely terminating randomized algorithms can be handled with additional limit arguments, but those are not needed for this stated version. The uniform distribution is a proof device for locating a hard fixed input, not an assumption about real-world inputs.
Accounting for records and range encodings
Counting sort commonly sorts records with satellite data, such as names attached to integer scores. Stability concerns those records: equal scores must retain their original order. The counter array stores counts of key values; the output array stores the records or references to them. If copying a whole record costs more than one unit, the operation cost must include that representation detail.
The parameter is the size of the key universe, not the number of distinct keys that happen to appear. If keys range from a known integer minimum to a maximum , subtracting gives indices from zero through , and the array length is . Computing or storing a huge range can dominate the input size. In a bit model, representing a key and performing arithmetic on it may also cost more than a single unit; the stated bound is for a word-level array-indexing model.
A comparison algorithm can exploit existing order in a particular input, and an integer algorithm can exploit a small key universe. These are different sources of structure. The worst-case lower bound remains applicable whenever arbitrary distinct keys can only be ordered by binary comparisons, even if some individual inputs happen to be easy.
For or , there is only one relative order and the lower bound is zero comparisons. The asymptotic statement concerns growing and does not require evaluating at zero. Counting sort can likewise return an empty output when , while still paying for any explicitly initialized count array.
Summary
A comparison sort must have enough binary decision-tree leaves to distinguish orders, yielding a worst-case comparison bound. Counting sort uses direct integer indexing and runs in time under a different model, with stability obtained by reverse traversal.
Exercises
Quick check
(How many leaves can a binary decision tree of height four have at most?)
Each level at most doubles the number of branches.
Solution · Answer
At most . Some leaves may be at smaller depths, but this cannot increase the maximum.
Quick check
(What lower bound does the leaf argument give for sorting four distinct keys?)
Count the relative orders and compare with powers of two.
Solution · Answer
There are relative orders. Since , some input requires at least five comparisons.
Quick check
(For keys , give the count array and the sorted key sequence.)
Use the key range , so .
Solution · Answer
For key range , the counts are and the sorted keys are .
Quick check
(Why does scanning the input right to left preserve equal-key record order in counting sort?)
Think about which equal-key record is placed first.
Solution · Answer
Each key's output block is filled from right to left as its prefix counter decreases. The later input record is encountered first and receives the later position, so the earlier record remains earlier in the output.