Comparison Sorting Has an Omega(n log n) Lower Bound
What This Concept Is
A comparison sorter for n distinct keys must distinguish n! possible relative orders. Model a deterministic algorithm as a binary decision tree: each internal node compares two keys, and each leaf identifies a permutation. A height-h tree has at most 2^h leaves, so worst-case comparisons are at least ceil(log2(n!)). For n at least 2, this is Omega(n log n).
No input probability distribution is needed for this worst-case statement. The average-case version needs a distribution, commonly uniform over the n! permutations. Under that distribution, average leaf depth is at least log2(n!).
Why It Matters Here
Lower bounds tell you what cannot be improved without changing the problem or the computational model. Finding one rank, sorting restricted keys, exploiting a known input family, and approximating a result are different tasks. They cannot be dismissed with a lower bound for unrestricted comparison sorting.
Concrete Examples
For three distinct items there are six possible orders. Two comparisons offer at most four binary outcomes, so some input requires at least three comparisons. For general n, at least the largest floor(n/2) factors in n! are at least n/2. Their logarithms alone give floor(n/2) log2(n/2), which is Omega(n log n). The upper bound n! <= n^n gives O(n log n), establishing the order without a precise Stirling approximation.
With a known multiset having multiplicities n1,...,nr, the distinguishable key orders number n!/(n1!...nr!). All-equal input has only one key order. This explains why adaptive or duplicate-aware algorithms can use less work on restricted inputs. Reading or writing all records can still require linear work.
Common Confusion / Misconceptions
"Both bounds assume random inputs" is false: only the stated average-case bound does. Nor does the worst-case bound require every input to take n log n comparisons. Counting sort uses integer keys as array indices, an operation the comparison-only model does not grant. Randomization cannot give a uniformly sub-n-log-n expected comparison sorter over all distinct-key inputs: condition on a random choice sequence and apply the average decision-tree argument.
How To Use It
When evaluating an alleged improvement, name its key universe, allowed operations, output contract, and whether the claim is worst-case, average-case, or expected over internal randomness. Check whether the method actually sorts, merely partitions, returns an approximation, or assumes preprocessed input.
Check Yourself
- Which assumption is unnecessary for the worst-case proof?
- Why does finding a minimum avoid the sorting lower bound?
- How do duplicate keys change the number of distinguishable orders?
- Why does indexing a count array change the model?
Mini Drill or Application
Draw a decision tree sorting three named distinct keys. Verify every leaf's output and locate a deepest path. Then analyze a promise that the input is either already sorted or reverse sorted: explain why a lower bound for unrestricted permutations does not apply to that promise. See P3.
Read This Only If Stuck
Use CLRS, Skiena, or Sedgewick and Wayne for comparison decision trees and sorting lower bounds. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.