THE FOLD / CHEAT / GOD MODE / THE MEDIAN OF MEDIANS
THE MEDIAN OF MEDIANS
pick the k-th smallest in guaranteed linear time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Median of medians finds the k-th smallest element in guaranteed linear time — O(n) worst case, not just on average. The trick is choosing a provably good pivot: split the array into groups of five, take each group’s median, then recursively take the median of those medians. That pivot is guaranteed to beat at least 30% of the elements on each side, so the recursion shrinks fast enough to stay linear — no adversarial input can force it to be slow.
LIT verified live: over 3000 random arrays, the element it selects for rank k equals the true k-th smallest from a full sort (window.__medianofmedians). FIG no framing; exact selection compared against sorting.
LIT verified live: over 3000 random arrays, the element it selects for rank k equals the true k-th smallest from a full sort (window.__medianofmedians). FIG no framing; exact selection compared against sorting.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at god-mode — take no damage from bad input: the median-of-medians pivot guarantees linear time no matter how adversarial the array. AVAN (AI) built the instrument: the groups-of-five median pivot, the three-way partition recursion, and the match against a full sort.
Credit as content: Blum, Floyd, Pratt, Rivest & Tarjan (1973) — the BFPRT algorithm. The weave: David names god-mode; I pick the pivot as the median of group-of-five medians, partition, recurse into the side holding rank k, and confirm the selected element is exactly the k-th smallest a full sort would give — linear time, worst-case guaranteed.
Credit as content: Blum, Floyd, Pratt, Rivest & Tarjan (1973) — the BFPRT algorithm. The weave: David names god-mode; I pick the pivot as the median of group-of-five medians, partition, recurse into the side holding rank k, and confirm the selected element is exactly the k-th smallest a full sort would give — linear time, worst-case guaranteed.
3 ONE DIMENSION
Group into fives, take each median, then the median of those. That pivot beats ≥ 3 of every 5 in half the groups — ≥ 30% overall — guaranteeing the recursion shrinks by a constant fraction. Linear, always.
4 TWO DIMENSIONS · INTERACTIVE
An array with its groups of five, the chosen pivot, and the selected k-th element checked against a sort.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the k-th smallest in guaranteed linear time.
AVAN’s addition (the inverse-companion): guarantee a good pivot without sorting — take medians of groups of five, then the median of those, so at least 30% falls on each side and the recursion is provably linear. The inverse of ‘sort everything to find the k-th’ is ‘pick a certified-balanced pivot and recurse into one side only.’ Magenta is the full sort; green is the single partition path. Selection that can’t be made slow.
LIT Genuine median-of-medians selection, the BFPRT algorithm (Blum, Floyd, Pratt, Rivest & Tarjan 1973). Verified live: over 3000 random arrays and ranks, the groups-of-five median-of-medians pivot with three-way partition recursion selects exactly the k-th smallest element that a full sort gives (window.__medianofmedians.matchesSort).
FIG No framing: the groups-of-five median pivot, the three-way partition recursion, and the match against a full sort run in-browser and agree. The AVAN inverse is honest — guaranteeing a balanced pivot (medians of fives, then their median → ≥30% each side) so selection is provably linear genuinely replaces sorting everything; magenta is the full sort, green the single partition path. Selection that can't be made slow.
FIG No framing: the groups-of-five median pivot, the three-way partition recursion, and the match against a full sort run in-browser and agree. The AVAN inverse is honest — guaranteeing a balanced pivot (medians of fives, then their median → ≥30% each side) so selection is provably linear genuinely replaces sorting everything; magenta is the full sort, green the single partition path. Selection that can't be made slow.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GOD MODE · David Lee Wise (ROOT0), with AVAN