Linear time selection — median of medians algorithm: Visual walkthrough

Everything here supports Quickselect — the algorithm that needs a good pivot — so keep that in the back of your mind.

Step 1 — What is a "pivot" and why can it ruin us?

WHAT. A pivot is one element we choose from the array. We then split every other element into two piles: those smaller than the pivot, and those larger. This split is called partitioning (see Partitioning (Lomuto vs Hoare)). After partitioning, the pivot sits at its true sorted position.

WHY. In Quickselect we only recurse into the pile that contains our target rank $k$ . So the size of the surviving pile is what determines speed. A pivot near the middle throws away ~half the array each time. A pivot at the extreme throws away just one element.

PICTURE. Look at the two number lines below. The magenta dot is the pivot.

Figure — Linear time selection — median of medians algorithm

Top line: pivot in the middle → both piles are small → fast.
Bottom line: pivot is the minimum → the "larger" pile is almost the entire array → we barely shrink → slow.

Here $n$ is the number of elements, and $f$ is the fraction of the array that could remain after one partition.

Step 2 — Lay the array into columns of 5

WHAT. Take all $n$ elements and place them into columns, 5 elements per column. If $n = 45$ that's exactly 9 columns. If $n$ isn't a multiple of 5, the very last column simply holds the 1–4 leftover elements — we keep it, giving $⌈ n /5 ⌉$ columns in all.

WHY. We are about to find a "typical" element cheaply. Sorting 5 numbers is constant work (a fixed number of comparisons regardless of how big $n$ grows), so finding the median of a column costs $O (1)$ . Doing this for every column costs $O (n)$ total — no logarithms, no sorting of the whole array.

PICTURE. Each column is drawn vertically. We will sort within each column so the smallest element is at the bottom and the largest at the top.

Each full column has 5 slots.
The middle slot of each column (position 3 of 5) is the column's median — highlighted in orange.

Step 3 — Find the median of the orange medians → that's $M$

WHAT. Collect all the orange medians (one per column). There are $\frac{n}{5}$ of them (exactly $⌈ n /5 ⌉$ ). Find their median. Call it $M$ .

WHY. $M$ is our pivot. Finding the median of $\frac{n}{5}$ numbers is itself a selection problem — so we call Select recursively on that smaller list. This recursion is the price we pay for a guaranteed central pivot (a purely random pick, as in Randomized algorithms, is cheaper but gives no guarantee).

PICTURE. The orange medians are pulled out into a row and their median $M$ is circled in violet.

$\frac{n}{5}$ = number of columns = number of medians.
$M$ = the median of that row = our pivot.

Because $M$ is the median of the medians, half of the orange medians are $\leq M$ , and the other half are $\geq M$ . Hold onto that fact — it powers the next two steps.

Step 4 — Sort the columns by their median (a thought-experiment)

WHAT. Imagine sliding the whole columns left-to-right so their orange medians increase from left to right. We never actually do this in code — it's a picture to reveal a hidden structure.

WHY. Once columns are ordered by median, a beautiful region appears: a rectangle of elements every one of which we can prove is $\leq M$ . That rectangle is the source of the $\frac{3 n}{10}$ guarantee.

PICTURE. After this imaginary sort:

Columns whose median is $\leq M$ sit on the left half.
Inside each such column, the median and the two elements below it (3 of the 5) are $\leq$ that column's median $\leq M$ .
Those cells form the shaded lower-left block — every element in it is $\leq M$ .

This is the key visual: an entire block of guaranteed-small elements, not just scattered ones.

Step 5 — Count the shaded block → the number $\frac{3 n}{10}$

WHAT. Count exactly how many elements are trapped in that lower-left block.

WHY. This count is the guaranteed size of the "smaller" pile. If it's a fixed fraction of $n$ , then the surviving (larger) pile is at most $n$ minus that fraction — a fraction strictly below 1.

PICTURE. The block is a grid; we count rows × columns.

By perfect symmetry (flip "smaller" to "larger", "below" to "above"), at least $\frac{3 n}{10}$ elements are also $\geq M$ .

Step 6 — Assemble the recurrence and watch it collapse

WHAT. Add up the work done in a single Select call:

building columns + column medians: $c n$ (linear scan),
recursing to find $M$ among $\frac{n}{5}$ medians: $T (\frac{n}{5})$ ,
recursing into the survivor of size $\leq \frac{7 n}{10}$ : $T (\frac{7 n}{10})$ .

WHY. This is a recurrence. Its shape decides linear vs. quadratic. The basic Master Theorem doesn't apply directly, because it assumes all subproblems have the same size, whereas ours are two different fractions ( $\frac{1}{5}$ and $\frac{7}{10}$ ). Generalized divide-and-conquer results (like the Akra–Bazzi method) can handle unequal splits, but the substitution below is shorter and shows exactly why it's linear — so we verify by substitution.

PICTURE. The recursion tree, with the total work per level shrinking geometrically.

Step 7 — The degenerate cases (nothing left unshown)

WHAT. Handle the corners where the tidy story wobbles.

WHY. A guarantee is only a guarantee if it survives every input — tiny arrays, non-multiples of 5, and duplicate pivots.

PICTURE. Three mini-scenarios side by side.

Tiny array ( $n \leq 5$ ). No recursion needed — just sort the $\leq 5$ elements and return the $k$ -th. This is the base case that stops the recursion (left panel).
$n$ not a multiple of 5. There are $⌈ n /5 ⌉$ columns; the last holds 1–4 elements. Even-size rule: for a column of 2 or 4, define its median as the lower-middle element (position $⌈ s /2 ⌉$ of a sorted size- $s$ column). This choice is fixed once and for all, so "the median" is never ambiguous. The block count then uses $⌊ \frac{1}{2} ⌈ n /5 ⌉⌋$ full columns and still gives at least $\approx \frac{3 n}{10}$ small elements; the floors and ceilings only shrink the survivor further, so the $< 1$ conclusion is only made safer (middle panel).
Duplicates equal to $M$ . Partition into three piles: $L$ (less than $M$ ), $E$ (equal to $M$ ), $G$ (greater than $M$ ). The Select code changes as follows: if $k \leq ∣ L ∣$ recurse into $L$ ; else if $k \leq ∣ L ∣ + ∣ E ∣$ return $M$ immediately (no recursion); else recurse into $G$ with rank $k - ∣ L ∣ - ∣ E ∣$ . Because we stop the moment $k$ lands in $E$ , a pile made entirely of copies of $M$ is never recursed on. Both piles we do recurse on ( $L$ and $G$ ) exclude all copies of $M$ , so each is strictly smaller than $n$ and still bounded by $\frac{7 n}{10}$ — the linear bound holds even when the input is almost all duplicates (right panel — the violet $E$ block).

The one-picture summary

This single frame stacks the whole argument: columns of 5 → orange medians → violet $M$ → the shaded $\frac{3 n}{10}$ block → survivor $\leq \frac{7 n}{10}$ → recurrence $T (n /5) + T (7 n /10) + c n$ → $\frac{9}{10} < 1$ → $O (n)$ .

Recall Feynman retelling — say it like you'd explain to a friend

We want the $k$ -th smallest number but we refuse to sort everything. The trick from Quickselect is to pick a pivot and toss the half that can't hold our answer. The danger: a bad pivot tosses almost nothing. So instead of guessing, we manufacture a safe pivot. We herd the numbers into little groups of 5, grab each group's middle number, then find the middle of those middles — that's $M$ . Now here's the magic: because $M$ is a median-of-medians, we can point at a whole rectangle of numbers we know are smaller than $M$ — about three-tenths of everything — and by symmetry three-tenths are bigger. So whichever side we recurse into holds at most seven-tenths of the array. Add up the work: one small recursion on a fifth of the data (to find $M$ ), one on at most seven-tenths (the survivor), plus a linear sweep. The two fractions, a fifth and seven-tenths, add to nine-tenths — less than one. Because each level of the recursion does strictly less work than the one above, the whole thing sums to a constant times $n$ : linear time, guaranteed, no luck required. When $n$ isn't a multiple of 5, we round up the number of columns and pick the lower-middle of any short column; that rounding only makes the winning inequality safer.