= Median of medians
For deterministic linear-time <selection>, group keys into fives, compute the median of each group, and recursively select the median of those medians as a pivot. Apart from bounded end effects, at least $3n/10$ keys lie on either side. Thus the selection cost satisfies $T(n)\leq T(\lceil n/5\rceil)+T(7n/10+O(1))+O(n)=O(n)$, since the fractions sum to $9/10<1$. A <strong induction> with sufficiently large linear coefficient absorbs the lower-order terms.
Back to article page
