Worked examples — Linear time selection — median of medians algorithm

This page drills the median-of-medians algorithm until no input can surprise you. We march through every case class the algorithm meets — the ordinary median, the exact-pivot hit, the extreme minimum, arrays clogged with duplicates, arrays too small to group, and the exam-style "prove the bound" twist.

Nothing here assumes you already trust the algorithm. Each example rebuilds the moving parts: the groups of 5, the group medians, the median of those medians (our pivot $M$), and the 3-way partition into $L$ (less), $E$ (equal), $G$ (greater).

The scenario matrix

Every worked example below is tagged with the matrix cell it exercises. Together the eight examples touch every cell.

Example 1 — $k$ lands exactly on the pivot (cell C1)

Forecast: After we pick pivot $M$, will $k=7$ land in $L$, $E$, or $G$? Guess the pivot's final sorted index — and whether we recurse at all.

1. Group into fives. [12,3,5,7,19] [1,8,22,4,6] [15,9,2,11,17]. Why this step? Constant-size groups make each group median $O(1)$ — the whole speed argument rests on this.
2. Median of each group (sort 5, take position $\lceil 5/2\rceil =3$). [3,5,7,12,19]→7, [1,4,6,8,22]→6, [2,9,11,15,17]→11. Why this step? These three medians are "typical" representatives of their groups.
3. Median of medians. Of [7,6,11], sorted [6,7,11], position $\lceil 3/2\rceil =2$ → $M=7$. Why this step? $M$ is our provably-not-extreme pivot (see Order statistics).
4. 3-way partition around 7. $L=[3,5,1,4,6,2]$ ($|L|=6$), $E=[7]$, $G=[12,19,8,22,15,9,11,17]$. Why this step? The pivot's sorted position is $|L|+1=7$.
5. Route $k$. Is $k=7\le |L|=6$? No. Is $k\le |L|+|E|=7$? Yes → the answer is exactly $M=7$. We recurse nowhere. This is the "$k$ hits the pivot" case.

The figure below sorts $A$ and colors the three buckets, so you can see that $k=7$ (red arrow) points straight at the orange pivot bar — the algorithm halts the instant $k$ enters $E$.

Verify: Sort $A$ → [1,2,3,4,5,6,7,8,9,11,12,15,17,19,22]; the 7th value is $7$, equal to $M$. ✅

Example 2 — $k$ small, recurse left (cell C2)

Forecast: Does $k=3$ stay inside $L$? Does the target index change when we recurse?

1. Reuse the pivot $M=7$, $L=[3,5,1,4,6,2]$, $|L|=6$. Why this step? The pivot depends on $A$, not on $k$ — so it's identical to Ex 1.
2. Route $k$. $k=3\le |L|=6$, so recurse left into $L$ with target unchanged: $k^{\prime }=3$. Why this step? Everything in $L$ is smaller than everything in $E\cup G$, so ranks inside $L$ match global ranks. No subtraction.
3. Solve inside $L=[3,5,1,4,6,2]$. Sorted: [1,2,3,4,5,6]; the 3rd is $3$.

Verify: Global sorted array's 3rd element is $3$. ✅ (And note we did not subtract anything — the classic C2 trap.)

Example 3 — $k$ large, recurse right (cell C3)

Forecast: After routing right, what is the adjusted target? Guess before computing.

1. Pivot $M=7$, $|L|=6$, $|E|=1$.
2. Route. $k=13>7$, recurse into $G=[12,19,8,22,15,9,11,17]$ with $k^{\prime }=13-(6+1)=6$. Why this step? We already skipped past the 7 elements $\le M$; the 13th overall is the 6th of what's left.
3. Solve inside $G$. Sorted $G$: [8,9,11,12,15,17,19,22]; the 6th is $17$.

Verify: Global sorted 13th element is $17$. ✅

Example 4 — even number of medians, pivot near an extreme (cell C4)

Forecast: How much does pivot $=1$ throw away? With only 2 group-medians, which one does our convention pick? And is the "$3n/10$" bound exact for $n=10$, or does a floor sneak in?

1. Bad pivot $p=1$. $L=[]$, $E=[1]$, $G=[2,\dots ,10]$ (9 elements). We removed one element for $O(n)$ work. Why this step? If every pivot were the min, cost $=n+(n-1)+\cdots =O(n^2)$ — exactly what Quickselect risks in the worst case.
2. Honest MoM pivot — apply the median convention. Groups [1,2,3,4,5]→3 and [6,7,8,9,10]→8, so the medians list is [3,8] with $m=2$ items. Our rule picks position $\lceil 2/2\rceil =1$ → the lower middle → $M=3$. Why this step? Two medians is exactly the ambiguous even case; the convention (fixed above) makes $M=3$ deterministic rather than a coin flip.
3. Guarantee with the honest floor. The clean "$3n/10$" formula is an asymptotic bound; for a specific small $n$ we must floor the counts. Here half the $\lceil n/5\rceil =2$ medians is 1 group whose median and the two below it are $\le M$, giving $\ge 3\cdot 1=3$ candidates — but that count includes $M$ and elements outside strict $L$. Concretely $L=[1,2]$ so $|L|=2$, $E=[3]$: the elements $\le M$ number $|L|+|E|=3$, matching $\lfloor 3n/10\rfloor =3$. The strict-less set can be smaller — the guarantee counts $\le M$, not $<M$. Why this step? The reviewer-style off-by-one comes from confusing "$\le M$" (which is $3$) with "strictly $<M$" (which is $2$). The theorem bounds $\le M$.
4. Surviving side. $G=[4,\dots ,10]$ has $7$ elements, and $\lfloor 7n/10\rfloor =7$. Exactly on the bound.

The figure contrasts the two pivots side by side: the orange bar is the pivot, and you can see the honest MoM pivot ($M=3$) leaves at most 7 green survivors, whereas $p=1$ leaves 9.

Verify: number of elements $\le M$ is $3=\lfloor 3\cdot 10/10\rfloor$; strict $|L|=2$; survivors $=7=\lfloor 7\cdot 10/10\rfloor$; and the even-median rule gives $M=3$. ✅

Example 5 — a swamp of duplicates (cell C5)

Forecast: If $M=5$ and most of the array equals 5, does the 2-way "$<$ / $\ge$" split loop forever? Why does the 3-way split save us?

1. Groups of 5. [5,5,5,5,5]→5, [5,5,2,9,5] sorted [2,5,5,5,9]→5. Medians [5,5], $m=2$, position $\lceil 2/2\rceil =1$ → $M=5$.
2. 3-way partition. $L=[2]$ ($|L|=1$), $E=[5,5,5,5,5,5,5,5]$ ($|E|=8$), $G=[9]$ ($|G|=1$). Why this step? A naive "less-than / greater-or-equal" split would dump all eight 5's on one side and recurse on a 9-element subproblem that never shrinks — an infinite/quadratic trap. The $E$ bucket absorbs the ties.
3. Route $k$. Is $k=8\le |L|=1$? No. Is $k\le |L|+|E|=9$? Yes → the answer is $M=5$.

Verify: Sort $A$ → [2,5,5,5,5,5,5,5,5,9]; 8th element $=5$. ✅

Example 6 — degenerate base case (cell C6)

Forecast: Does the grouping loop run at all here?

1. Base-case check. Since $n=5\le 5$, we do not group. We sort directly and index. Why this step? Grouping into fives with one group is pointless; sorting 5 items is constant work. This is the recursion's floor.
2. Sort and index. Sorted: [3,7,7,42,99]; the 4th (1-indexed) is $42$.

Verify: sorted([42,7,7,99,3])[4-1] == 42 ✅

Example 7 — leftover group when $n\mathrm{mod}5\ne 0$ (cell C7)

Forecast: How big is the last group, and what is the median of a 3-element group?

1. Group into fives, last group short. [20,4,17,9,1] [14,6,11,2,8] [19,15,7]. The last group has only 3 elements — that's fine. Why this step? Real arrays rarely divide evenly; the median of a short group is just its middle after sorting.
2. Group medians (position $\lceil m/2\rceil$). [1,4,9,17,20]→9, [2,6,8,11,14]→8, [7,15,19]→15. Medians [9,8,15].
3. Median of medians. Of [9,8,15], sorted [8,9,15], position $\lceil 3/2\rceil =2$ → $M=9$.
4. Partition around 9. $L=[4,1,6,2,8,7]$ ($|L|=6$), $E=[9]$, $G=[20,17,14,11,19,15]$.
5. Route $k=6$. $k=6\le |L|=6$ → recurse left into $L$, target unchanged $k^{\prime }=6$. Sorted $L$: [1,2,4,6,7,8]; 6th is $8$.

Verify: Sort $A$ → [1,2,4,6,7,8,9,11,14,15,17,19,20]; the 6th element is $8$. ✅

Example 8 — word problem + exam-twist bound (cell C8)

Forecast: Which $k$ is the 95th percentile? What fraction does one level shave off?

1. Translate percentile to $k$. The 95th percentile is the $k$-th order statistic with $k=\lceil 0.95\cdot n\rceil =950,000$. Why this step? Order statistics turns "percentile" into "which sorted index" — a plain selection query.
2. Why MoM, not random? The requirement says hard worst-case. Randomized Quickselect is $O(n)$ only in expectation; an adversarial or unlucky ordering gives $O(n^2)$. MoM's guarantee is unconditional.
3. Bound the surviving side. At least $\frac{3n}{10}$ elements are $\le M$ and at least $\frac{3n}{10}$ are $\ge M$, so each side is at most $n-\frac{3n}{10}=\frac{7n}{10}$. For $n=10^6$: $\frac{7n}{10}=700,000$. Why this step? This is the inequality that caps how much can survive to the next level.
4. Total work. By the recurrence $T(n)\le T(n/5)+T(7n/10)+cn$ and $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1$, so $T(n)=O(n)$ — the hard budget is honored.

The recursion-tree figure plots the work at each level as a fraction of $n$; each bar is $\frac{9}{10}$ of the previous, so the bars form a shrinking geometric series that sums to $10n$ — visibly linear.

Verify: $\lceil 0.95\cdot 10^6\rceil =950000$ ✅ and $7\cdot 10^6/10=700000$ ✅ and $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1$ ✅

Recall

Flashcards