The Comparison-Sorting Lower Bound
Any sort that only compares pairs of elements is a decision tree with n factorial leaves, so its height is at least n log n. This is a statement about every possible algorithm, not about the ones anybody has written.
What a learner can do afterwards
- Draw the decision tree of a comparison sort on three elements and count its leaves
- Argue from the leaf count to a bound on the tree's height
- Explain how counting sort beats the bound without contradicting it
1 · Read
A comparison sort learns only by comparing pairs of items. Picture its work as a decision tree, where each branch is one compare result and each leaf is one final order.
Take three distinct items. They can arrive in 6 orders, which is 3 factorial, so the tree needs at least 6 leaves, one leaf per order. A tree of height 2 holds at most 4 leaves, so height 2 is not enough.
For n items there are n factorial orders, so any comparison tree needs n factorial leaves. Its height is at least log base 2 of n factorial, which grows like n log n. That height is a floor, called big-Omega, that every comparison sort must reach. Mergesort and heapsort touch that floor, so they are as fast as any comparison sort can ever be.
Counting sort can run faster because it changes the rules and reads values instead of comparing pairs. That beats the floor without breaking it, since the floor only covers comparing sorts.
Comparing sorts need n factorial leaves, so they cost at least n log n, and only non comparing methods can dodge that floor.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.