Overview
Median of Medians groups values, finds medians of those groups, and recursively chooses a robust pivot for selection.
ExtendedSource checked
Median of Medians
Selects a pivot that guarantees linear-time selection in the worst case.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Advanced
- Family
- Deterministic Selection
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
order statisticdeterministic pivotrank partitiondivide and conquer
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(log n)
When to Use
- Use when selection needs a worst-case guarantee rather than only expected performance.
- Use when worst-case linear selection is a central requirement.
When Not to Use
- Avoid when constant factors matter more than adversarial worst-case behavior.
- Avoid when the input does not preserve the ordering or rank assumption the search relies on.
What It Does
- Groups values into small blocks
- Selects a guaranteed-good pivot
- Narrows the search by rank
Use Cases
- Worst-case linear selection
- Robust pivot choice
- Finding exact order statistics
Inputs
- Array or list of comparable values
- Requested rank
Outputs
- Value at the requested rank
Key Formulas (1)
Selection recurrence
T(n) ≤ T(n/5) + T(7n/10) + O(n)
T(n) <= T(n/5) + T(7n/10) + O(n)Captures why the deterministic pivot still gives linear worst-case selection.
Pseudocode
- 1.Split values into groups of five
- 2.Sort each group and collect its median
- 3.Recursively select the median of those medians
- 4.Partition around that pivot
- 5.Continue only in the partition containing the requested rank
Canonical Example
- Input
- values = [9, 1, 8, 2, 7, 3, 6], rank = 3
- Output
- value = 6
- Explanation
- The algorithm chooses a robust pivot and keeps only the side containing the fourth-smallest value.
Implementation Notes
- Use three-way partitioning so values equal to the pivot are handled cleanly.
- Test lower, upper, duplicate, empty, and not-found cases separately.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Partitioning incorrectly around equal values can destroy the rank calculation.
- Boundary conditions around equal values and missing values are easy to handle inconsistently.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow groups producing medians, then a pivot that discards a guaranteed fraction of values.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Split values into groups of five
array-searchNotes
The method is important for guarantees, though randomized Quickselect is often faster in practice.
Sources (2)
What each reference supports for this entry.
BFPRT Selection
PaperOriginal deterministic linear-time selection paper using median-of-medians pivots.
Open sourceIntroduction to Algorithms (CLRS)
BookAlgorithms textbook support for Median of Medians's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byQuickselect
Median of medians can choose deterministic pivots for worst-case linear-time selection.
Related Algorithms
Tags
SearchSelectionDivide and ConquerOrder Statistic