The Sorting Lower Bound

Why sort?

Sorting is one of the most deeply studied topics in algorithm design. Common applications:

Application	Why sorting helps
Search	Sorted data admits binary search: O(log n) vs. O(n)
Merging	Two sorted lists can be merged in linear time
Duplicates	After sorting, duplicates become adjacent and easy to find
Inverting tables	A directory sorted by name can be re-sorted by phone number
Graphics	Many rendering algorithms require sorted input

Information-theoretic lower bound

How many comparisons are needed to sort n items? Consider the decision tree model:

• There are n! possible permutations of n distinct elements.
• Each comparison eliminates roughly half of the remaining possibilities.
• With C(n) comparisons, we can distinguish at most 2^{C(n)} outcomes.

For the algorithm to be correct for all inputs, we must have:

$$2^{C(n)} \geq n!$$

Taking logarithms:

$$C(n) \geq \log_2(n!) \approx n \log_2 n - 1.44n$$

This is the information-theoretic lower bound: any comparison-based sorting algorithm must perform at least O(n log n) comparisons in the worst case. Mergesort achieves this bound exactly, making it asymptotically optimal.

Beyond comparisons

The lower bound applies only to comparison-based sorting. Non-comparison sorts (e.g., radix sort) can achieve O(n) time for certain restricted inputs, such as integers within a fixed range. This does not contradict the lower bound because such algorithms exploit properties of the data beyond pairwise comparisons.