Linear-Time Selection

How do you find the median of $n$ numbers? The obvious answer, sorting them and reading off the middle, costs $\Theta (n\log n)$. But the median, and more generally the $k$-th smallest element, can be found in linear time.¹ The insight is that selection asks for less than sorting: we want one element's value, not the full ordering, and we can stop as soon as we have it.

The selection problem

Special cases: $k=1$ is the minimum, $k=n$ the maximum, and $k=\lfloor (n+1)/2\rfloor$ the median. The minimum and maximum are easy in $n-1$ comparisons. The median is the interesting case, and the algorithms below solve it as a byproduct of solving general selection.

Quickselect: partition, then recurse on one side

Quicksort partitions around a pivot and recurses on both halves. But for selection we only care about one of them. After partitioning $A[p..r]$ around a pivot that lands at index $q$, the pivot is the $(q-p+1)$-th smallest element of the subarray. Compare that rank to $k$:

• if it equals $k$, the pivot is the answer;
• if $k$ is smaller, the answer lies in the left part, so recurse there;
• if $k$ is larger, the answer lies in the right part; recurse there, adjusting $k$ to skip the elements we discarded.

Throwing away the side that cannot contain the answer is what turns $\Theta (n\log n)$ into $\Theta (n)$.²

Expected linear time

Partition costs $\Theta (n)$. The win over quicksort is that we recurse on only one side. With a randomized pivot, the partition splits the array at a uniformly random rank, so on average we discard a constant fraction each time. Intuitively, a random pivot lands in the middle half of the array with probability $1/2$, in which case the surviving side has at most $3n/4$ elements. The expected work satisfies, roughly,

a geometric (not branching) recurrence. Unrolling it,

The geometric series converges to a constant, so the total is linear. (A careful CLRS-style analysis with indicator variables gives the same $\mathbb{E}[T(n)]=O(n)$.)

The catch is the same as quicksort's: the worst case, with every pivot maximally unbalanced, is

Randomization makes that astronomically unlikely, but it is still possible. Can we guarantee linear time?

Median of medians: a guaranteed-good pivot

The deterministic algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan (1973) achieves worst-case $O(n)$ by spending a little effort to choose a pivot that is provably not too extreme.³ The trick is to pick the pivot as a median of medians.

Why groups of five give a good pivot

Here is the core of it. Picture the $\lceil n/5\rceil$ groups as columns, each sorted top (large) to bottom (small), and now imagine the columns reordered left to right by their medians. The pivot $x=\text{MoM}$ is the median of that middle row, so it sits dead-center in the grid below. (We assume distinct elements for simplicity.)

The pivot is built in stages: chop the array into groups of five, sort each group to expose its median, collect those $\lceil n/5\rceil$ medians, and recurse to find their median — the median of medians.

Consider the columns whose median is $\ge x$: that is, $x$'s own column and the roughly half of the $\lceil n/5\rceil$ columns to its right. In each such column, the median and the two elements above it (the two larger ones) are all $\ge x$. That is 3 elements per column, across about half of the $n/5$ columns:

So at least $\approx 3n/10$ elements are $\ge x$, which forces at most$n-3n/10=7n/10$ to be $<x$. By the symmetric argument (the dashed block) at least $\approx 3n/10$ are $\le x$, so at most $\approx 7n/10$ are $>x$. Whichever side we recurse into has at most $\approx 7n/10$ elements, so the pivot is provably never too lopsided. (Five is the smallest odd group size that makes the recurrence below close; groups of $3$ fail because their fractions sum to exactly $1$.)

Solving the recurrence

Tallying the work: splitting into groups and finding their medians is $O(n)$ (each group is sorted in $O(1)$). Partitioning is $O(n)$. There are two recursive calls:

• finding the median of the $\lceil n/5\rceil$ medians, a subproblem of size $n/5$;
• recursing into the surviving side, a subproblem of size at most $7n/10$.

The two fractions are what make this work. Observe that $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1$: the two subproblems together are strictly smaller than the input. That is shrinkage — the total work contracts by a constant factor at every level.

For inspiration, first consider the single-call cousin $f(n)\le f(n/2)+bn$. The master theorem gives $f(n)=O(n)$; unrolling shows why directly,

The constant-factor-shrinkage plus linear cleanup work sums to $O(n)$. The median-of-medians recurrence has two calls instead of one, but the same shrinkage idea carries it through. State it as a clean general lemma:

Plugging in $\lambda =\frac{1}{5}$, $\mu =\frac{7}{10}$ (so $\lambda +\mu =\frac{9}{10}$) gives $T(n)=O(n)$, that is, worst-case linear time. Had the fractions summed to $1$ or more (as for groups of $3$, where $\frac{1}{3}+\frac{2}{3}=1$), the lemma's hypothesis fails: the per-level savings vanish, the recursion tree carries $\log n$ levels of $\Theta (n)$ work, and the bound degrades to $\Theta (n\log n)$.

Which to use

The median-of-medians algorithm is a landmark: it proves selection is possible in worst-case linear time. But its constant factor is large (all that grouping and recursive median-finding), so in practice randomized quickselect is faster and is the algorithm of choice.⁴ The deterministic version shines when a worst-case guarantee is mandatory, or, most importantly, as a pivot-selection subroutine that can be bolted onto quicksort to give it a worst-case $\Theta (n\log n)$ bound.

Bonus: Closest Pair of Points

This is often called the most beautiful divide-and-conquer algorithm, and also the scariest to get right. It is worth seeing because, like median-of-medians, its speed hinges on a geometric counting argument that caps how much work the combine step can possibly do.

We treat one distance computation and one distance comparison as $O(1)$. The naïve algorithm, two nested loops over all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs, runs in $\Theta (n^2)$. Can divide-and-conquer beat it?

The idea, and the trap

Split $P$ by the median $x$-coordinate into a left half and a right half, recurse on each to get the closest pair within each side, and let $\delta$ be the smaller of the two returned distances. The danger is the combine step: the true closest pair might straddle the dividing line, so we still have to look across it.

The trap is doing this naïvely. If $n_L$ left points and $n_R$ right points lie near the line, checking every cross pair costs $\Theta (n_L\cdot n_R)$, which can be $\Theta (n^2)$, no better than brute force. The whole game is to show that only $O(n)$ cross-comparisons are ever needed.

The $\delta$-strip and the 7-neighbor bound

Any cross pair closer than $\delta$ must have both points within horizontal distance $\delta$ of the dividing line, i.e. inside a vertical strip of width $2\delta$. So discard everything outside the strip. Then sort the strip's points by $y$-coordinate and walk up it; the magic is that for each point you only need to compare against the next 7 points in $y$-order.

Why 7? Fix a strip point $B[i]$ and look at the points $B[j]$ above it (larger $y$) that could beat $\delta$. Any such point lies in the $2\delta \times \delta$ box sitting just above $B[i]$ inside the strip. Tile that box with a grid of $\delta /2\times \delta /2$ cells — there are exactly 8 of them.

So the box holds at most $8$ points, one of which is $B[i]$ itself: at most $7$ candidates. Hence in $y$-sorted order it suffices to compare $B[i]$ with $B[i+1],\dots ,B[i+7]$ — a constant number of checks per point. The combine step is $O(n)$, not $\Theta (n^2)$.

The algorithm

The whole thing rests on having the points pre-sorted both ways. Sort once by $x$ (call it $AX$) and once by $y$ ($AY$) up front; the recursion then threads these sorted orders down without re-sorting.

Running time and correctness

The split, the strip extraction, and $\text{Best-Pair}$ are each $O(n)$, and there are two half-size recursive calls:

by the master theorem, the same shape as mergesort. The initial sorts add a one-time $O(n\log n)$, so the total stays $O(n\log n)$.

Correctness is an easy induction on $n$, given that $\text{Best-Pair}$ finds any closest cross-strip pair. That assumption is exactly the 7-neighbor claim above: for each $B[i]$, every later strip point that could improve on $\delta$ lies in one of the $7$ cells of $B[i]$'s grid (the cell holding $B[i]$ aside), and each cell holds at most one point — so scanning $B[i+\mathrm{1..}i+7]$ cannot miss it.

• Selection finds the $k$-th smallest element; it needs less than sorting, so it can run in $O(n)$.
• $\text{Quickselect}$ = quicksort's partition, but recurse into only the side that holds the answer; expected $O(n)$ via a geometric (non-branching) recurrence, worst case $\Theta (n^2)$.
• Median of medians chooses a provably balanced pivot using groups of five, guaranteeing the recursion drops at least $\approx 3n/10$ elements per side.
• That balance yields $T(n)\le T(n/5)+T(7n/10)+O(n)$, and because $\frac{1}{5}+\frac{7}{10}<1$, the recurrence solves to worst-case $O(n)$.
• In practice randomized quickselect wins on constants; median-of-medians matters for guarantees and as a quicksort pivot rule.
• Closest pair of points is divide-and-conquer with the same flavor: split by median $x$, recurse on each half, then combine over a width-$2\delta$ strip. A geometric argument caps the strip work at $7$ comparisons per point, giving $T(n)\le 2T(n/2)+O(n)=O(n\log n)$.