Median of Medians (BFPRT)

Sorting a list answers every order question at once — but it is also overkill. If you only need the k-th smallest element (the median, the 90th percentile, the second-largest), sorting is doing far more work than necessary.

The naive remedy is quickselect: partition the array around a pivot, then recurse only into the half that contains rank k. On random data this runs in $O(n)$ expected time. But a malicious input — or even an unlucky pivot choice — can degrade it to $O(n^{2})$. For a long time it was an open question: can you find the k-th smallest element in guaranteed $O(n)$ time, without sorting?

In 1973, Manuel Blum, Robert Floyd, Vaughan Pratt, Ronald Rivest, and Robert Tarjan (BFPRT) answered yes. Their algorithm — now called median of medians — selects a pivot so carefully that the array is always split into at least a constant fraction on each side, guaranteeing $O(n)$ worst-case time no matter what the input looks like.

The idea is beautifully recursive: to find a good pivot for selecting from n elements, first find the exact median of a smaller set derived from n — and that smaller selection problem is solved by the same algorithm.

The demo below runs the full BFPRT pivot-selection procedure on a random array. Press Step to advance one phase at a time, or Run All to watch it finish instantly.

<p class="hint">{{hint}}</p>
<div id="array-display" class="array-display"></div>
<div id="phase-label" class="phase-label">{{press_step}}</div>
<div id="groups-display" class="groups-display"></div>
<div id="info" class="info-box"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.array-display { display: flex; flex-wrap: wrap; gap: 4px; margin-bottom: .5rem; min-height: 44px; }
.cell {
  width: 38px; height: 38px; display: flex; align-items: center; justify-content: center;
  font: 700 13px ui-monospace, monospace; border-radius: 6px; border: 1px solid #cdd9e3;
  background: #e8eef3; color: #1d3557; transition: background .2s;
}
.cell.active { background: #457b9d; color: #fff; border-color: #1d3557; }
.cell.pivot { background: #e63946; color: #fff; border-color: #c92f3c; }
.cell.median { background: #2a9d8f; color: #fff; border-color: #1f7c70; }
.cell.done { background: #c8e6c9; color: #1b5e20; border-color: #81c784; }
.phase-label { font-weight: 700; font-size: .95rem; color: #1d3557; margin-bottom: .4rem; min-height: 1.3em; }
.groups-display { display: flex; flex-wrap: wrap; gap: 8px; margin-bottom: .5rem; min-height: 0; }
.group-box { border: 1.5px solid #a8c0d6; border-radius: 8px; padding: 4px 6px; background: #f0f6fb; }
.group-box .group-label { font-size: .75rem; color: #457b9d; font-weight: 700; margin-bottom: 2px; }
.group-box .group-cells { display: flex; gap: 3px; }
.group-box .gcell {
  width: 32px; height: 32px; display: flex; align-items: center; justify-content: center;
  font: 700 12px ui-monospace, monospace; border-radius: 5px; border: 1px solid #cdd9e3;
  background: #e8eef3; color: #1d3557;
}
.group-box .gcell.med { background: #2a9d8f; color: #fff; border-color: #1f7c70; }
.info-box { font-size: .88rem; color: #333; background: #f7f9fb; border: 1px solid #cdd9e3;
            border-radius: 8px; padding: .5rem .7rem; margin-bottom: .6rem; min-height: 2.2em;
            line-height: 1.5; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Each phase is labeled: grouping elements into blocks of five, finding each block's median by sorting the block, then recursively finding the median of those medians. The chosen pivot is highlighted, and you can see the lower bound on how many elements are guaranteed to be smaller — always at least ⌈3n/10⌉ − 6, which is the key to the $O(n)$ proof.

Status: solved. Blum, Floyd, Pratt, Rivest, and Tarjan proved in 1973 that selection can be done in $O(n)$ worst-case time. This is also optimal — any comparison-based algorithm must read every element at least once, so Ω(n) is a lower bound.

The proof hinges on a geometric counting argument about the pivot:

1. Divide the n elements into groups of five (the last group may be smaller).
2. Sort each group — only five elements, so this costs $O(1)$ per group, $O(n/5)$ total.
3. Find the median of the n/5 group medians — by a recursive call to the same algorithm.
4. Use that median-of-medians as the pivot to partition the full array.
5. Recurse into the relevant partition.

Why does the pivot work? Each group has five elements; its median beats at least two of its own group. Those medians in turn: half of the n/5 medians are below the overall median-of-medians (since we found its true median). Counting carefully, at least ⌈3n/10⌉ − 6 elements are guaranteed less than the pivot, and the same number are guaranteed greater. So neither partition can be larger than about 7n/10.

The recurrence is:

T(n) ≤ T(⌈n/5⌉) + T(⌊7n/10⌋ + 6) + $O(n)$

The two recursive calls cover at most n/5 + 7n/10 = 9n/10 < n elements in total. By substitution one verifies T(n) = $O(n)$.

Compare to sorting algorithms: sorting needs Ω(n log n) comparisons in the comparison model; selection is strictly easier. Median of medians also shows that randomized algorithms are not necessary for linear-time selection — a deterministic strategy achieves the same bound, though with a larger constant.

Knowing the k-th smallest without sorting is useful wherever you need a rank but not the full order:

• Databases: SELECT … ORDER BY salary LIMIT 10 OFFSET 90 effectively asks for a percentile. Linear-time selection avoids a full sort on huge tables.
• Streaming statistics: computing the running median or a percentile over a data stream requires efficient order-statistic maintenance — median-of-medians provides the theoretical backbone.
• Balanced pivot for introsort: real-world sorting libraries (like C++ std::sort) use introsort, which falls back to heapsort after too many bad partitions. Median-of-medians is the canonical guaranteed-good pivot when the depth limit is hit.
• Computational geometry: many geometric algorithms (ham-sandwich cuts, point-in-halfspace queries) rely on finding medians in linear time to achieve their $O(n \log n)$ or $O(n)$ bounds.
• Machine learning: splitting a k-d tree optimally requires the median of a coordinate — $O(n)$ median finding makes tree construction faster.

The algorithm itself is rarely deployed verbatim in production (its constant factor is high), but it is the theoretical benchmark: any selection algorithm that claims to beat it in the worst case must prove $O(n)$, and median of medians sets that bar. See also sorting lower bounds for the companion result on comparison-based sorting.

The median-of-medians algorithm is one of the cleanest results in algorithm design: a problem (find the k-th smallest) that looks like it should require sorting turns out to be strictly cheaper. Five authors in 1973 showed that a recursive pivot strategy — find the median of the medians of groups of five — is enough to guarantee a balanced partition every time.

The $O(n)$ bound is tight. You cannot do better in the comparison model, because you must inspect every element. But you also do not need to sort — and that gap, from $O(n \log n)$ down to $O(n)$, is the whole point.

Next time you reach for sort() just to grab a percentile, remember: there is a smarter path, and it has been proven optimal for over fifty years.