Overview

This chapter establishes a fundamental lower bound showing that no comparison-based sort can do better than Ω(n lg n) in the worst case, then presents three algorithms—counting sort, radix sort, and bucket sort—that bypass this barrier by exploiting properties of the input beyond pairwise comparisons. These linear-time sorts demonstrate that when additional assumptions about the data hold (integer keys in a known range, fixed-length digit representation, or uniform distribution), sorting can be achieved in Θ(n) time.

Key Concepts

• Comparison sort model: Any sort that determines order solely by comparing pairs of elements (e.g., merge sort, heapsort, quicksort). All such algorithms obey the Ω(n lg n) lower bound.
• Decision-tree model: An abstraction where each internal node represents a comparison (aᵢ ≤ aⱼ), each leaf represents one of the n! permutations of the input, and the height of the tree equals the worst-case number of comparisons. Any correct comparison sort's decision tree must have at least n! reachable leaves.
• Non-comparison sorts: Counting sort, radix sort, and bucket sort use information beyond element comparisons—such as digit values or distribution properties—to sort faster than Ω(n lg n).
• Stability: A sort is stable if elements with equal keys retain their original relative order in the output. Stability is critical for radix sort's correctness, since it sorts digit-by-digit from least significant to most significant, relying on earlier passes' ordering being preserved.

Algorithms and Techniques

8.1 — Lower Bounds for Comparison Sorting (Decision-Tree Argument)

The chapter opens by proving that every comparison sort must perform at least Ω(n lg n) comparisons in the worst case. The argument proceeds via the decision-tree model:

1. Model any comparison sort on n elements as a binary decision tree.

2. Each leaf corresponds to a permutation of the input; a correct sort must have all n! permutations reachable.

3. A binary tree of height h has at most 2ʰ leaves, so n! ≤ 2ʰ.

4. Taking logarithms: h ≥ lg(n!) = Ω(n lg n) (using Stirling's approximation).

This establishes Theorem 8.1: any comparison sort requires Ω(n lg n) comparisons in the worst case.

Corollary 8.2: Merge sort and heapsort, which run in O(n lg n) worst-case time, are asymptotically optimal among comparison sorts.

8.2 — Counting Sort

Idea: Given n integers each in the range 0 to k, determine for every element x how many elements are ≤ x, then place x directly into its correct output position.

How it works (COUNTING-SORT(A, B, k)):