Why Ω(n lg n) is a hard floor for comparison sorting, and three algorithms that get underneath it by refusing to compare.
Three sorts so far, all Θ(n lg n), none better. Chapter 8 proves that is no accident: any algorithm that determines the sorted order using only comparisons needs Ω(n lg n) comparisons in the worst case. The proof is a counting argument over decision trees and it is short, general, and complete — it rules out not just the algorithms we have seen but every algorithm of that kind that will ever be written. The rest of the chapter escapes the bound by making assumptions about the keys themselves: counting sort, radix sort, and bucket sort all run in linear time by extracting information from keys without comparing them.
aᵢ < aⱼ, aᵢ ≤ aⱼ, aᵢ = aⱼ, aᵢ ≥ aⱼ, or aᵢ > aⱼ. It may not inspect the values in any other way.Insertion sort, merge sort, heapsort, and quicksort are all comparison sorts. So is every general-purpose sort() that takes a comparator function — the comparator is literally the only window it has onto the data.
Two simplifying observations make the analysis clean. First, we may assume all elements are distinct, since ties only make sorting easier and we are after a lower bound. Second, given distinctness, all five comparison forms are equivalent in the information they yield, so we may assume every comparison is of the form aᵢ ≤ aⱼ.
Abstract away everything except the comparisons. A decision tree is a full binary tree representing the comparisons performed by a particular sorting algorithm on inputs of a given size.
i:j, meaning “compare aᵢ with aⱼ”.aᵢ ≤ aⱼ; the right subtree when aᵢ > aⱼ.⟨π(1), π(2), …, π(n)⟩, the sorted order the algorithm concludes.Two facts follow immediately from this correspondence:
Ω(n lg n) lower boundΩ(n lg n) comparisons in the worst case.The proof is three lines of counting.
Step 1: the tree needs at least n! leaves. A correct sorting algorithm must be able to produce every one of the n! permutations of its input, since any one of them could be the right answer. Each permutation must appear as at least one reachable leaf. So the number of reachable leaves is at least n!.
Step 2: a binary tree of height h has at most 2ᵗ leaves. Elementary.
Step 3: combine and take logarithms.
n! ≤ 2h
h ≥ lg(n!)
= Θ(n lg n) // Stirling's approximation, Chapter 3
h = Ω(n lg n)The step lg(n!) = Θ(n lg n) is the one piece of real mathematics, and Chapter 3 already supplied it from Stirling’s approximation. Intuitively: n! has n factors, most of them larger than n/2, so n! is at least (n/2)n/2 and its logarithm is at least (n/2)lg(n/2) = Ω(n lg n).
O(n lg n) upper bounds match the Ω(n lg n) lower bound to within a constant factor.lg(n!) bits to identify one permutation out of n!; therefore you need lg(n!) comparisons. Information-theoretic arguments of this shape recur throughout complexity theory.Assumption: every input element is an integer in the range 0 to k, for some known k.
The idea: for each input value x, count how many elements are less than or equal to x. That count is the final position of x. No comparisons required — just array indexing.
COUNTING-SORT(A, B, n, k)
1 let C[0:k] be a new array
2 for i = 0 to k
3 C[i] = 0
4 for j = 1 to n
5 C[A[j]] = C[A[j]] + 1
6 // C[i] now holds the number of elements equal to i
7 for i = 1 to k
8 C[i] = C[i] + C[i-1]
9 // C[i] now holds the number of elements less than or equal to i
10 for j = n downto 1 // backwards, for stability — see below
11 B[C[A[j]]] = A[j]
12 C[A[j]] = C[A[j]] - 1Four loops: initialise, tally, accumulate a running total, then place. Output goes to a separate array B, so this is not in place.
k = 5. The cumulative array says “there are 7 elements ≤ 3”, so the last 3 goes to slot 7. Decrement and the next 3 goes to slot 6.Running time. The loops cost Θ(k), Θ(n), Θ(k), Θ(n), so the total is Θ(n + k). When k = O(n) this is Θ(n) — genuinely linear.
k = O(n). Sorting a million 32-bit integers with counting sort means k = 2³², so Θ(n + k) is four billion operations and a 16 GB count array to sort a million values. Use it when the key range is small and known: ages, bytes, grades, day-of-year, priority levels.Counting sort is stable: elements with equal keys appear in the output in the same order they appeared in the input. That property is not incidental, and it is the entire reason line 10 counts downward.
Walk it through. C[3] = 7 means seven elements are ≤ 3, so the last 3 in the input belongs in slot 7. Scanning the input from the right, the first 3 encountered is the last one, and it correctly claims slot 7. Decrementing C[3] to 6 means the next 3 encountered — which came earlier in the input — claims slot 6. Earlier input elements get earlier output slots. Stability preserved.
for j = 1 to n and the algorithm still sorts correctly, but equal elements come out in reverse input order. That breaks radix sort, which depends on the stability of its digit sort. This is the one-character change that quietly destroys the next algorithm in the chapter.Counting sort needs a small key range. Radix sort removes that limitation by sorting d-digit numbers one digit at a time, using a stable sort on each digit.
RADIX-SORT(A, n, d)
1 for i = 1 to d
2 use a stable sort to sort array A[1:n] on digit iDigit 1 is the least significant. Counter-intuitively, you sort from the least significant digit upward, not the most significant.
i: after sorting on digit i, the array is sorted on the low-order i digits. When the pass on digit i+1 runs, elements that differ on that digit are ordered correctly by the sort; elements that tie on it keep their previous relative order, which by the inductive hypothesis was correct on the lower digits. Remove stability and every tie scrambles the work of all previous passes, and the algorithm is simply wrong.Running time. With d digits each in range 0 to k, using counting sort per pass:
T(n) = Θ( d·(n + k) ) // Θ(n) when d is constant and k = O(n)The chapter also asks how to choose the digit size. Given n numbers of b bits each, split each into b/r digits of r bits, so k = 2ᵣ - 1:
T(n, b) = Θ( (b/r)·(n + 2ᵣ) )Choosing r ≈ lg n balances the two terms and gives Θ(bn / lg n). For 32-bit keys and a million elements, that means four passes of 8 bits each — the standard configuration in real radix sort implementations.
Θ(bn/lg n) where quicksort is Θ(n lg n) in comparisons that often stop after a few bytes. It uses Θ(n + k) extra space and has poor locality. It wins convincingly on large volumes of fixed-width integer keys, and loses on short arrays, variable-length keys, and anything needing a custom comparator.Assumption: the input is drawn independently and uniformly from [0, 1).
Divide [0,1) into n equal-sized buckets, drop each element into its bucket, sort each bucket with insertion sort, and concatenate.
BUCKET-SORT(A, n)
1 let B[0:n-1] be a new array of empty lists
2 for i = 1 to n
3 insert A[i] into list B[⌊n·A[i]⌋]
4 for i = 0 to n-1
5 sort list B[i] with insertion sort
6 concatenate lists B[0], B[1], …, B[n-1] in orderExpected running time Θ(n). Lines 1–4 and 6 are Θ(n). For line 5, let nᵢ be the number of elements in bucket i; insertion sort costs O(nᵢ²). Under the uniformity assumption nᵢ is binomial with mean 1, and E[nᵢ²] = 2 - 1/n, so the expected total for line 5 is Θ(n).
| Sort | Time | Space | Stable | Requires |
|---|---|---|---|---|
| Insertion | Θ(n²), Θ(n) if nearly sorted | Θ(1) | Yes | Comparisons |
| Merge | Θ(n lg n) | Θ(n) | Yes | Comparisons |
| Heap | Θ(n lg n) | Θ(1) | No | Comparisons |
| Quick (rand.) | Θ(n lg n) expected | Θ(lg n) | No | Comparisons |
| Counting | Θ(n + k) | Θ(n + k) | Yes | Integer keys in 0..k |
| Radix | Θ(d(n + k)) | Θ(n + k) | Yes | Keys as d digits |
| Bucket | Θ(n) expected | Θ(n) | Yes | Uniform over a known range |
a less than b?”, so the decision-tree model does not describe them and its bound does not bind them. Extra assumptions about the keys buy you extra speed.n! leaves and a height-h binary tree has at most 2ᵗ, so h ≥ lg(n!) = Ω(n lg n). Merge sort and heapsort are asymptotically optimal.Θ(n + k), stable, not in place. Linear only when k = O(n).Θ(d(n+k)). Stability is not optional — without it each pass destroys the previous ones.n buckets over a uniform range, insertion sort each, concatenate. Θ(n) expected.Chapter 9 asks a related question: if you only want the ith smallest element, must you pay for a full sort? No. Randomized selection finds any order statistic in expected Θ(n) time by partitioning like quicksort but recursing on only one side, and the median-of-medians algorithm achieves Θ(n) in the worst case.