THE FOLD / CHEAT / THE SPEEDRUN / THE QUICKSELECT
THE QUICKSELECT
the k-th smallest in O(n) — median of medians
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Quickselect finds the k-th smallest element without fully sorting: partition around a pivot and recurse into only the side that holds the k-th element — expected O(n). The refinement median of medians (Blum–Floyd–Pratt–Rivest–Tarjan) guarantees O(n) worst case: split into groups of 5, take each group’s median, recursively find the median of those medians, and use it as pivot — a provably good pivot that shrinks the problem by a constant fraction each time.
It is how you compute a median in guaranteed linear time.
LIT verified live: over 300 random arrays, median-of-medians quickselect returns exactly sorted[k] for every k (window.__quickselect). FIG no framing; exact selection.
It is how you compute a median in guaranteed linear time.
LIT verified live: over 300 random arrays, median-of-medians quickselect returns exactly sorted[k] for every k (window.__quickselect). FIG no framing; exact selection.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the k-th element in O(n) instead of an O(n log n) sort. Quickselect is the order-statistic speedrun. AVAN (AI) built the instrument: the median-of-medians pivot, the one-sided recursion, the check against a full sort.
Credit as content: Tony Hoare (quickselect, 1961); Blum, Floyd, Pratt, Rivest & Tarjan (median-of-medians, 1973). The weave: David names the speedrun; I pick a provably-good pivot by finding a median of medians, recurse into a single side, and confirm the returned element is exactly the k-th smallest.
Credit as content: Tony Hoare (quickselect, 1961); Blum, Floyd, Pratt, Rivest & Tarjan (median-of-medians, 1973). The weave: David names the speedrun; I pick a provably-good pivot by finding a median of medians, recurse into a single side, and confirm the returned element is exactly the k-th smallest.
3 ONE DIMENSION
Partition around a pivot: smaller elements left, larger right. The k-th element lies in exactly one side, so recurse there and discard the other — half or more of the work thrown away each step.
4 TWO DIMENSIONS · INTERACTIVE
An array and a target rank k. Median-of-medians selects the k-th smallest, shown against the sorted array; only the containing side is recursed, far fewer comparisons than a full sort.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the recursion shrinking to the side that contains the k-th element, converging on one value.
AVAN’s addition (the inverse-companion): you get the answer without the order. Quickselect delivers exactly one order statistic while leaving the rest of the array only partially arranged — because you never need the full sort, just the position of one element. The inverse of ‘sort then index’ is ‘index without sorting.’ And median-of-medians’ worst-case guarantee is self-referential: to pick a good pivot it finds a median (of medians) — a smaller instance of the very problem being solved — so the algorithm uses recursion to guarantee its own efficiency. Magenta is the full sorted order you never compute; green is the single k-th element and the partial partition around it. The whole is unnecessary for the part.
LIT Genuine quickselect + median-of-medians (Hoare 1961; Blum, Floyd, Pratt, Rivest & Tarjan 1973). Verified live: the median-of-medians pivot with one-sided recursion returns exactly sorted[k] for every k across 300 random arrays (window.__quickselect.matchesSorted).
FIG No framing: the median-of-medians pivot, the one-sided recursion, and the check against a full sort run in-browser and agree exactly. The AVAN inverse is honest — you get one order statistic without the full order, and median-of-medians' worst-case guarantee is self-referential (it finds a median of medians, a smaller instance of the same problem); magenta is the never-computed full sort, green the single k-th element.
FIG No framing: the median-of-medians pivot, the one-sided recursion, and the check against a full sort run in-browser and agree exactly. The AVAN inverse is honest — you get one order statistic without the full order, and median-of-medians' worst-case guarantee is self-referential (it finds a median of medians, a smaller instance of the same problem); magenta is the never-computed full sort, green the single k-th element.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN