Show that there is no comparison sort whose running time is linear for at least half of the \(n!\) inputs of length \(n\). What about a fraction of \(1/n\) of the inputs of length \(n\)? What about a fraction \(1/2^n\)?
We’ll use the decision tree model to analyze this problem. The key insight is that even if some inputs can be sorted quickly, the structure of the decision tree forces most inputs to require many comparisons.
Consider a decision tree for sorting \(n\) elements. It must have at least \(n!\) leaves (one for each possible permutation). Let \(h\) be the height of the tree and \(d\) be some depth less than \(h\).
The number of leaves at depth \(d\) or less is at most \(2^d\) (since it’s a binary tree). If we want a fraction \(f\) of all \(n!\) permutations to be sorted in \(O(d)\) time, we need:
\[2^d \geq f \cdot n!\]Taking logarithms:
\[d \geq \lg(f \cdot n!) = \lg f + \lg(n!)\]A. Fraction \(f = 1/2\)
For half the inputs to run in \(O(d)\) time:
\[\begin{align*} d &\geq \lg(1/2) + \lg(n!) \\ &= -1 + \Theta(n \lg n) \\ &= \Theta(n \lg n) \end{align*}\]So even if half the inputs could be sorted at depth \(d\), we’d still need \(d = \Theta(n \lg n)\), which is not linear.
B. Fraction \(f = 1/n\)
\[\begin{align*} d &\geq \lg(1/n) + \lg(n!) \\ &= -\lg n + \Theta(n \lg n) \\ &= \Theta(n \lg n) \end{align*}\]Again, \(d = \Theta(n \lg n)\), not linear.
C. Fraction \(f = 1/2^n\)
\[\begin{align*} d &\geq \lg(1/2^n) + \lg(n!) \\ &= -n + \Theta(n \lg n) \\ &= \Theta(n \lg n) \end{align*}\]Even for this tiny fraction, \(d = \Theta(n \lg n)\).
The conclusion is striking: no comparison sort can have linear time for any significant fraction of inputs. The \(\Omega(n \lg n)\) lower bound dominates even when we allow all but an exponentially small fraction of inputs to run slowly.