Argue that for any constant \(0 < \alpha \leq 1/2\), the probability is approximately \(1 - 2\alpha\) that on a random input array, \(\textsc{Partition}\) produces a split more balanced than \(1-\alpha\) to \(\alpha\).
What makes a partition worse than \(1-\alpha\) to \(\alpha\)
A partition is worse than (more unbalanced than) \(1-\alpha\) to \(\alpha\) when one side has fewer than \(\alpha n\) elements. This happens when:
- The pivot is one of the smallest \(\alpha n\) elements (creating a left partition with fewer than \(\alpha n\) elements), or
- The pivot is one of the largest \(\alpha n\) elements (creating a right partition with fewer than \(\alpha n\) elements).
Since \(\alpha \leq 1/2\), these two ranges don’t overlap. The “bad” pivots are:
- The smallest \(\alpha n\) elements (positions 1 through \(\alpha n\))
- The largest \(\alpha n\) elements (positions \((1-\alpha)n + 1\) through \(n\))
The total number of bad pivot choices is approximately \(\alpha n + \alpha n = 2\alpha n\).
Probability of a good split
Since the pivot is chosen uniformly at random from \(n\) elements, and approximately \(2\alpha n\) choices lead to bad splits:
\[\begin{align*} \Pr[\text{good split}] &= 1 - \Pr[\text{bad split}] \\ &= 1 - \frac{2\alpha n}{n} \\ &= 1 - 2\alpha \end{align*}\]Example
With \(\alpha = 1/10\) (meaning we want a split at least as balanced as 9-to-1):
- Bad splits occur when the pivot is in the smallest 10% or largest 10%
- Probability of a good split: \(1 - 2(1/10) = 0.8 = 80\%\)
This result shows that balanced partitions are actually quite likely. Even requiring a fairly balanced split (say, 9-to-1), we still get a good partition 80% of the time. This is why randomized quicksort performs well in practice.