249. Why can no comparison-based sort beat Ω(n log n) in the worst case?
MediumSorting
Show model answer
Model any comparison sort as a binary decision tree: each internal node is one comparison and each leaf is one output ordering. To sort correctly, every one of the n! permutations of distinct inputs must reach a different leaf, so the tree has at least n! leaves. A binary tree with L leaves has height at least log₂ L, so the worst-case number of comparisons is at least log₂(n!).
By Stirling’s approximation log₂(n!) = n log₂ n − n log₂ e + O(log n) = Θ(n log n). The same argument applies to the average case because the average leaf depth of a binary tree with n! leaves is also at least log₂(n!). Counting, radix and bucket sort escape the bound because they inspect key values directly instead of only comparing pairs.