median-of-medians selection

To split an array well with quickselect or quicksort, you want a pivot near the middle — but you do not know the middle without already doing the work. Median-of-medians is a clever bootstrapping trick that produces a provably good pivot quickly, guaranteeing worst-case linear time for selection. It is the algorithm that turns 'find the k-th smallest element' from a gamble into a guarantee.

The pivot-choosing procedure: divide the n elements into groups of five; find the median of each group (trivial, since five elements sort in constant time); then recursively apply the whole selection algorithm to those n/5 group-medians to find their median — the 'median of medians'. Use that value as the pivot. The magic is a counting argument: this pivot is guaranteed to be greater than at least 3/10 of the elements and less than at least 3/10, so partitioning around it discards at least about 30% of the array every time. The recurrence becomes T(n) = T(n/5) + T(7n/10) + O(n): one recursive call to pick the pivot on a fifth of the data, one on the surviving at-most-70%, plus linear partition work. Because 1/5 + 7/10 = 9/10 is strictly less than 1, this solves to O(n) — linear in the worst case.

Median-of-medians, due to Blum, Floyd, Pratt, Rivest and Tarjan (so the BFPRT algorithm), is a landmark: it proves selection can be done in deterministic linear time, with no randomness and no bad worst case. Its honest place in practice, though, is mostly theoretical: the constant factor hidden in that O(n) is large, so randomized quickselect, with expected O(n) and a tiny constant, is faster on real inputs almost always. Median-of-medians earns its keep as the safe pivot rule when an adversary controls the input or a guaranteed bound is required.