MEDIAN OF MEDIANS a pivot with a guarantee — deterministic O(n) selection
Quickselect is O(n) on average, but a bad pivot can drag it to O(n²). Median of medians (BFPRT, 1973) removes the luck: split the array into groups of five, take each group’s median, then recursively take the median of those medians as the pivot. That pivot is guaranteed to be greater than at least ~30% of elements and less than ~30%, so every partition throws away a constant fraction — giving deterministic O(n) selection, worst case. It is the theoretical guarantee behind fast selection, and a small marvel of self-reference: find a good pivot for finding by finding medians. Groups (7,1,5),(3,9,2),(8,4,6) give medians 5,3,6, whose median is 5.
THE TECHNIQUE medians of groups of 5, then their median — a provably good pivot
The demo takes group medians of (7,1,5),(3,9,2),(8,4,6) — 5,3,6 — then their median, 5: live demo
HISTORY & CREDIT Blum, Floyd, Pratt, Rivest, Tarjan · 1973
“Fast selection is only fast on average.” — median of medians gives a pivot guarantee, making selection O(n) worst case. cited
the groups · split into fives; take each group’s median (cheap, fixed size). the pivot · recursively take the median of the medians — guaranteed to split off a constant fraction. 1973 · Blum, Floyd, Pratt, Rivest, Tarjan — deterministic O(n) selection.
A pivot chosen by finding medians of medians — luck removed, O(n) guaranteed. resource
RECOMMEND FOR I-13 the pivot of pivots, on the compiler
On the canonical compiler, group medians 5, 3, 6 give a median-of-medians pivot of 5:
$ i13 run or_medianofmedians.i13 # median of group medians
RUN OK · 151 step(s) · peak stack 4 · call depth 1
m1 = 5 m2 = 3 m3 = 6 -- group medians
pivot = 5 -- median of the medians
is5 = 1
Recommend as a NULL — resource, via a guaranteed pivot. Median of medians computes a pivot that guarantees O(n) worst-case selection — a resource guarantee (B40); the pivot value is forall-pinned by the input (B39). The self-referential flavor (medians to find medians) is charming but not the fixed-point axis. NULL — the theoretical guarantee under fast selection.