The Comparison-Sort Lower Bound (Decision Trees)

Any deterministic algorithm that sorts $n$ distinct keys using only comparisons needs $\lceil \log_2(n!)\rceil = \Omega(n\log n)$ comparisons in the worst case, because its decision tree must have at least $n!$ leaves.