Questions
55 of 59
What is the Median of Medians algorithm? Why is it better than random pivot selection?
Difficulty: 5/10
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.
Follow-up Questions
- Why are groups of five used?
- Why can randomized Quickselect still be preferable in practice?