What is the Median of Medians algorithm? Why is it better than random pivot selection?

Difficulty: 7/10

selection algorithm, deterministic pivot, linear‑time guarantee

Median of Medians

Median of Medians is a deterministic selection algorithm that chooses a pivot with guaranteed quality. It divides elements into groups, commonly groups of five, finds each group's median, recursively finds the median of those medians, and partitions around that pivot. This guarantees linear worst-case time for selection, unlike randomized Quickselect, whose worst case is quadratic.

javascript

1
Provides deterministic O(n) worst-case selection.
2
Randomized Quickselect provides expected O(n).
3
Median-of-medians has higher constants in practice.
4
Useful when worst-case guarantees are more important than constant factors.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions