Skip to interview prep
Apexed

298. Explain the median-of-medians selection algorithm. Why groups of 5, and would groups of 3 or 7 work?

HardSearching & selection

Technical
Show model answer

Split the array into groups of 5, find each group’s median by brute force, recursively select the median of those ⌈n/5⌉ medians, and use it as the pivot. At least half of the groups have a median ≤ the pivot, and each such group contributes 3 elements ≤ the pivot, so about 3n/10 elements are on each side. The recursion then continues on at most about 7n/10 elements.

That gives T(n) ≤ T(n/5) + T(7n/10) + O(n). Because 1/5 + 7/10 < 1, the work shrinks geometrically and T(n) = O(n) in the worst case. With groups of 7 the recurrence is T(n/7) + T(5n/7) + O(n), and 1/7 + 5/7 < 1, so it is also linear. With groups of 3 it becomes T(n/3) + T(2n/3) + O(n), where the fractions sum to exactly 1, giving O(n log n).

The constants are large, so in practice random pivots (or introselect, which falls back to median of medians only when progress is poor) are faster.

Explain the median-of-medians selection algorithm. Why groups of 5, and would groups of 3 or 7 work — Data structures & algorithms interview question — Apexed