Comparison-Based Sorting Lower Bound¶

Any algorithm that sorts by pairwise comparisons requires at least Omega(n log n) comparisons in the worst case, because the decision tree must distinguish n! permutations.

Tension Addressed¶

Generality vs. Efficiency

Recognizable As¶

Any sorting algorithm using only less-than/greater-than operations; explains why merge sort and heapsort are asymptotically optimal for general comparison sorts.

Canonical Sources¶

Knuth, The Art of Computer Programming Vol. 3, 1973; CLRS, Introduction to Algorithms, Chapter 8, 2009

Transfers To¶

Information theory (log n! bits needed), decision theory, query complexity in any comparison-based system

This bound represents a mathematical limit, not an implementation constraint. Non-comparison sorts (counting, radix, bucket) bypass it by exploiting additional structure (bounded integers, uniform distribution) at the cost of generality.