---
title: Linear-Time Selection
module: Divide & Conquer
moduleNumber: 2
lessonNumber: 3
order: 203
summary: |
  Finding the $k$-th smallest element looks like it should require sorting, but
  it does not. Quickselect adapts quicksort's partition to recurse on just one
  side, achieving expected $O(n)$. The median-of-medians algorithm guarantees a
  good pivot with the groups-of-five trick, pushing the worst case down to a
  provable $O(n)$.
topics: [Order Statistics, Divide & Conquer]
sources:
  - book: CLRS
    ref: "Ch. 9 — Medians and Order Statistics"
  - book: Skiena
    ref: "§4 — Sorting and Searching"
  - book: Erickson
    ref: "Ch. 1 — Recursion"
practice:
  - title: 'Kth Largest Element in an Array'
    slug: kth-largest-element-in-an-array
    difficulty: Medium
  - title: 'K Closest Points to Origin'
    slug: k-closest-points-to-origin
    difficulty: Medium
  - title: 'Wiggle Sort II'
    slug: wiggle-sort-ii
    difficulty: Medium
  - title: 'Median of Two Sorted Arrays'
    slug: median-of-two-sorted-arrays
    difficulty: Hard
---

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.[^clrs-select] The
insight is that selection requires _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

> **Input:** an array $A[1..n]$ of $n$ distinct numbers and an integer $k$ with
> $1 \le k \le n$.
> **Output:** the element of $A$ that is larger than exactly $k - 1$ of the
> others — the **$k$-th order statistic**.

Special cases: $k = 1$ is the minimum, $k = n$ the maximum, and
$k = \floor{(n+1)/2}$ 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.

### Minimum and maximum together

The minimum alone costs $n - 1$ comparisons, and no algorithm can do better:
every element except the eventual winner must lose at least one comparison, so
$n - 1$ losses are unavoidable. Finding both the minimum _and_ the maximum
naively costs $2(n - 1)$ — run the minimum scan and the maximum scan
separately. But you can do it in about $3n/2$ by processing elements in
**pairs**. For each pair, compare the two against each other first ($1$
comparison), then send the smaller to the running minimum and the larger to the
running maximum ($2$ more). That is $3$ comparisons per $2$ elements, or
$3n/2$ total, versus $4n/2 = 2n$ for the separate scans. The saving comes from
never comparing the larger of a pair against the current minimum, nor the
smaller against the current maximum — half the comparisons in the naive method
are provably pointless.

## Quickselect: partition, then recurse on one side

[Quicksort](/algorithms/divide-and-conquer/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)$.[^erickson-qsel]

$$
% caption: Quickselect partitions once around $x$, then recurses into only the side
%          holding rank $k$ (here $k<i$, the left part) and discards the other.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % three regions; the pivot lands at its final rank i (= its sorted index)
  \draw[fill=acc!8]   (0,0)   rectangle (3.4,0.8);
  \draw[fill=acc!25, draw=acc, very thick] (3.4,0) rectangle (4.4,0.8);
  \draw[fill=red!8]    (4.4,0) rectangle (8.0,0.8);
  \node at (1.7,0.4) {$<\,x$};
  \node at (3.9,0.4) {$x$};
  \node at (6.2,0.4) {$>\,x$};
  % endpoints + pivot label
  \node[above] at (0,0.8)   {\footnotesize $p$};
  \node[above] at (8.0,0.8) {\footnotesize $r$};
  \node[above] at (3.9,0.85) {\footnotesize \texttt{pivot} at rank $i$};
  % left = the side holding rank k: recurse (accent)
  \draw[<->, acc] (0,-0.25) -- (3.4,-0.25) node[midway,below] {\footnotesize \texttt{A[p..i-1]}};
  \node[acc, font=\scriptsize] at (1.7,-0.92) {recurse (holds $k$)};
  % pivot's final index
  \draw[->] (3.9,-0.25) -- (3.9,-0.55) node[below] {\footnotesize $i$};
  % right = discarded side (red)
  \draw[<->, red!75!black] (4.4,-0.25) -- (8.0,-0.25) node[midway,below] {\footnotesize \texttt{A[i+1..r]}};
  \node[red!75!black, font=\scriptsize] at (6.2,-0.92) {discarded};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Quickselect}(A, p, r, k)$ — return the $k$-th smallest of $A[p..r]$
number: 1
if $p = r$ then
  return $A[p]$ // only element: the answer
$q \gets$ call $\textsc{Randomized-Partition}(A, p, r)$
$i \gets q - p + 1$ // pivot rank in A[p..r]
if $k = i$ then
  return $A[q]$ // pivot is the k-th smallest
else if $k < i$ then
  return call $\textsc{Quickselect}(A, p, q - 1, k)$ // recurse left
else
  return call $\textsc{Quickselect}(A, q + 1, r, k - i)$ // recurse right, shift k
```

::impl{algo="quickselect"}

### A worked trace

Take $A = [7,\,2,\,9,\,4,\,1,\,6,\,3,\,8,\,5]$ ($n = 9$) and ask for the
$k = 4$-th smallest. Suppose each call happens to pick the last element of its
range as the pivot.

The first partition uses pivot $5$. Everything smaller slides left, everything
larger slides right, and $5$ settles into the slot where it belongs:

$$
[\,\underbrace{2,\,4,\,1,\,3}_{<\,5}\,\mid\, 5 \,\mid\, \underbrace{7,\,9,\,6,\,8}_{>\,5}\,].
$$

The pivot landed at index $q = 5$, so its rank in the range is $i = 5$. We want
rank $k = 4 < 5$, so the answer is in the left part $[2,4,1,3]$ and we recurse
there with $k$ unchanged.

Partition $[2,4,1,3]$ around pivot $3$: $[\,2,\,1\,\mid\,3\,\mid\,4\,]$.
The pivot's rank in this range is $i = 3$. We still want rank $4$, and $4 > 3$,
so we recurse **right** into $[4]$ and shift the target to
$k - i = 4 - 3 = 1$.

That range has a single element, $4$, which is trivially its own $1$st smallest —
so $\textsc{Quickselect}$ returns $\mathbf{4}$. Checking against the sorted array
$[1,2,3,4,5,6,7,8,9]$: the $4$-th smallest is indeed $4$. At every step we
partitioned one range and then threw away everything on the wrong side of the
pivot, never sorting the parts we kept.

$$
% caption: Quickselect on $[7,2,9,4,1,6,3,8,5]$ seeking $k=4$. Each level partitions
%          around a pivot, keeps only the side holding rank $k$ (accent), and discards
%          the rest (faded); the target rank is re-based after every right recursion.
\begin{tikzpicture}[font=\footnotesize, >=Stealth, x=1cm, y=1cm,
  keep/.style={draw=acc, fill=acc!12, minimum width=6mm, minimum height=6mm, inner sep=0},
  drop/.style={draw=black, fill=black!4, text=black, minimum width=6mm, minimum height=6mm, inner sep=0},
  piv/.style ={draw=acc, very thick, fill=acc!30, minimum width=6mm, minimum height=6mm, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  % Level 0: full array, pivot 5 at the far right, k=4
  \foreach \v/\i in {7/0,2/1,9/2,4/3,1/4,6/5,3/6,8/7} \node[keep] at (\i,0) {$\v$};
  \node[piv] at (8,0) {$5$};
  \node[anchor=west, font=\footnotesize] at (8.7,0) {\texttt{pivot = 5, want k = 4}};
  % Level 1: after partition; left kept, pivot placed, right dropped
  \foreach \v/\i in {2/0,4/1,1/2,3/3} \node[keep] at (\i,-1.1) {$\v$};
  \node[piv] at (4,-1.1) {$5$};
  \foreach \v/\i in {7/5,9/6,6/7,8/8} \node[drop] at (\i,-1.1) {$\v$};
  \node[anchor=west, font=\footnotesize] at (8.7,-1.1) {\texttt{rank i = 5; 4 $<$ 5: go left}};
  % Level 2: partition [2,4,1,3] around pivot 3
  \foreach \v/\i in {2/0,1/1} \node[keep] at (\i,-2.2) {$\v$};
  \node[piv] at (2,-2.2) {$3$};
  \node[keep] at (3,-2.2) {$4$};
  \node[anchor=west, font=\footnotesize] at (8.7,-2.2) {\texttt{rank i = 3; 4 $>$ 3: go right, k = 1}};
  % Level 3: single element 4
  \node[piv] at (3,-3.3) {$4$};
  \node[anchor=west, font=\footnotesize] at (8.7,-3.3) {\texttt{one element: return 4}};
\end{tikzpicture}
$$

### 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,

$$
T(n) \le T(3n/4) + \Theta(n),
$$

a _geometric_ (not branching) recurrence. Unrolling it,

$$
T(n) \le c\!\parens{n + \tfrac{3}{4}n + \parens{\tfrac{3}{4}}^2 n + \cdots}
= cn \cdot \frac{1}{1 - 3/4} = 4cn = \Theta(n).
$$

The geometric series converges to a constant, so the total is linear.

The hand-wave above hides one step: why is the _expected_ surviving size a
constant fraction of $n$? With a uniformly random pivot, its rank is equally
likely to be any of $1,\dots,n$. Call the pivot **good** if its rank falls in the
middle half, between $n/4$ and $3n/4$; that happens with probability $1/2$. A
good pivot leaves at most $3n/4$ elements on either side. So on average we need
at most two partitions to shrink the range to $\le 3n/4$, and each partition
costs $O(n)$. That gives $\mathbb{E}[T(n)] \le \mathbb{E}[T(3n/4)] + O(n)$,
which unrolls to the geometric sum above. CLRS reaches the same
$\mathbb{E}[T(n)] = O(n)$ more carefully with indicator variables summed over
every possible pivot rank; the constant it extracts is small.

$$
% caption: A single-side recurrence shrinks the subproblem by a constant factor each
%          level, so the bars $n, \tfrac34 n, (\tfrac34)^2 n, \dots$ sum to a geometric
%          $\Theta(n)$.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \draw[fill=acc!30] (0,0) rectangle (6.0,0.5); \node[anchor=west, font=\scriptsize] at (6.15,0.25) {$n$};
  \draw[fill=acc!22] (0,-0.7) rectangle (4.5,-0.2); \node[anchor=west, font=\scriptsize] at (6.15,-0.45) {$\tfrac34 n$};
  \draw[fill=acc!16] (0,-1.4) rectangle (3.375,-0.9); \node[anchor=west, font=\scriptsize] at (6.15,-1.15) {$(\tfrac34)^2 n$};
  \draw[fill=acc!10] (0,-2.1) rectangle (2.53,-1.6); \node[anchor=west, font=\scriptsize] at (6.15,-1.85) {$(\tfrac34)^3 n$};
  \node[font=\scriptsize] at (1.0,-2.5) {$\vdots$};
  \node[anchor=west, acc, font=\scriptsize] at (6.15,-2.55) {sum $=4n$};
\end{tikzpicture}
$$

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

$$
T(n) = T(n - 1) + \Theta(n) = \Theta(n^2).
$$

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.[^clrs-mom] The idea is to pick the pivot as a **median of
medians**.

```algorithm
caption: $\textsc{Select}(A, k)$ — deterministic $k$-th smallest, worst-case $O(n)$
number: 2
if $A$ has at most $5$ elements then
  return the $k$-th smallest of $A$ by direct sorting
divide $A$ into $\ceil{n/5}$ groups of $5$ elements (last group may be smaller)
foreach group do
  find that group's median by sorting its $\le 5$ elements
let $M$ be the array of the $\ceil{n/5}$ group medians
$x \gets$ call $\textsc{Select}(M, \ceil{|M|/2})$ // median of medians
$q \gets$ partition $A$ around the pivot $x$, returning its rank $i$
if $k = i$ then
  return $x$
else if $k < i$ then
  return call $\textsc{Select}(A[\,\text{left part}\,], k)$
else
  return call $\textsc{Select}(A[\,\text{right part}\,], k - i)$
```

::impl{algo="median_of_medians"}

### Why groups of five give a good pivot

Here is the core of it. Picture the $\ceil{n/5}$ 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 = \textsc{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 $\ceil{n/5}$ medians, and **recurse**
to find _their_ median — the median of medians.

$$
% caption: Building the pivot: split into groups of $5$, sort each to surface its median
%          (accent cell), gather the $\ceil{n/5}$ medians, then recurse on that smaller
%          array to get the median of medians $x$.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm,
  cell/.style={draw, minimum width=5mm, minimum height=5mm, font=\scriptsize, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  % three sorted groups of five (columns): plain cells in rows 0,1,3,4 ...
  \foreach \gx in {0,1,2} {
    \foreach \r in {0,1,3,4} \node[cell] at (\gx, -\r*0.55) {};
  }
  % ... and the centre-row median highlighted per column
  \foreach \gx in {0,1,2} \node[cell, fill=acc!18, draw=acc, very thick] at (\gx,-1.1) {};
  \node[font=\footnotesize] at (1, 0.62) {\texttt{n/5} sorted groups};
  \node[font=\scriptsize, anchor=east, acc] at (-0.45,-1.1) {medians};
  % arrow: gather medians into a row
  \draw[->, red!75!black, thick] (2.55,-1.1) -- (3.45,-1.1);
  \node[font=\scriptsize, red!75!black] at (3.0,-0.7) {gather};
  % the gathered median array
  \foreach \x in {0,1,2} \node[cell, fill=acc!18, draw=acc, very thick] at (4+\x*0.55,-1.1) {};
  \node[font=\footnotesize] at (4.55,-0.5) {\texttt{n/5} medians};
  % arrow: recurse to find median of medians
  \draw[->, red!75!black, thick] (5.5,-1.1) -- (6.4,-1.1);
  \node[font=\scriptsize, red!75!black, align=center] at (5.95,-1.55) {recurse:\\Select};
  % the median of medians x
  \node[cell, fill=acc!30, draw=acc, very thick] at (6.95,-1.1) {};
  \node[font=\scriptsize, anchor=west] at (7.3,-1.1) {$x=$ MoM};
\end{tikzpicture}
$$

$$
% caption: Grid of groups of five with the median of medians $x$, showing the regions
%          guaranteed at least or at most $x$.
\begin{tikzpicture}[x=8mm, y=8mm]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!15] (-0.45,-2.45) rectangle (4.45,-1.55);
  % grid of dots
  \foreach \c in {0,...,4} {
    \foreach \r in {0,...,4} {
      \node[circle, fill=acc, inner sep=1.1pt] (n\c\r) at (\c,-\r) {};
    }
  }
  % the guaranteed >= x region (upper-right block): pivot + medians to its right + the two above each
  % (the median row runs through the pivot; leave a gap around it so the rule clears the $x$ glyph)
  \draw[thick, red] (1.5,0.5) -- (1.5,-2) -- (1.8,-2);
  \draw[thick, red] (2.2,-2) -- (4.5,-2);
  % the guaranteed <= x region (lower-left block)
  \draw[thick, red!60!black, dashed] (2.5,-4.5) -- (2.5,-2) -- (2.2,-2);
  \draw[thick, red!60!black, dashed] (1.8,-2) -- (-0.5,-2);
  % the median-of-medians: an empty circle marks its position; the $x$ label sits
  % fully OUTSIDE the grid (far right) with a long leader threaded between the dot
  % rows (y between -1 and -2) so it crosses no dots
  \node[draw=acc, circle, very thick, fill=acc!30, minimum size=4mm, inner sep=0] at (2,-2) {};
  \node[font=\scriptsize] at (5.5,-1.5) {$x$};
  \draw[->, thin] (5.25,-1.55) -- (2.2,-1.83);
  % region labels moved outside the grid, each with a leader arrow into its block
  \node[font=\footnotesize, anchor=west] at (5.0,-0.5) {each \texttt{$\ge$ x}};
  \draw[->, thin] (4.95,-0.5) -- (3.6,-0.6);
  \node[font=\footnotesize, anchor=east] at (-1.0,-3.6) {each \texttt{$\le$ x}};
  \draw[->, thin] (-0.95,-3.6) -- (0.4,-3.2);
  \node[font=\footnotesize, black] at (2.0,1.6) {\texttt{middle row (medians, incr.)}};
  \draw[->, black] (-0.7,-4.9) -- (-0.7,0.9);
  \node[font=\footnotesize, black, anchor=east] at (-0.9,-2) {\texttt{incr.}};
\end{tikzpicture}
$$

For example, take these $15$ numbers and split them into
three groups of five:

$$
\underbrace{[12,\,3,\,20,\,7,\,15]}_{G_1}\quad
\underbrace{[9,\,1,\,18,\,4,\,11]}_{G_2}\quad
\underbrace{[6,\,17,\,2,\,14,\,8]}_{G_3}.
$$

Sort each group and read off its median (the third of five):

$$
G_1 = [3,7,\mathbf{12},15,20],\quad
G_2 = [1,4,\mathbf{9},11,18],\quad
G_3 = [2,6,\mathbf{8},14,17].
$$

The three group medians are $\{12, 9, 8\}$. Their median is $x = 9$ — the
**median of medians**, our pivot. Now count what $9$ guarantees. Its own group
$G_2$ contributes $9$ and everything at or below it there ($1,4$) as elements
$\le 9$; $G_3$, whose median $8 < 9$, contributes its median and the two below
it ($2,6,8$) as elements $\le 9$. That already fixes $6$ of the $15$ values as
$\le 9$ before we even scan the array. Partitioning around $9$ therefore cannot
strand it near either end: the split is provably balanced. This is the
$\ge 3n/10$ guarantee in miniature — with $n = 15$, at least
$3 \cdot 15 / 10 \approx 4$ to $5$ elements are pinned to each side.

> **Claim (Pivot balance).** Whichever side $\textsc{Select}$ recurses into has
> at most $\approx 7n/10$ elements, so the median-of-medians pivot is provably
> never too lopsided.

> **Proof.** Consider the columns whose median is $\ge x$: that is, $x$'s own column and
> the roughly half of the $\ceil{n/5}$ 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:
> $$
> \#\set{\,\text{elements} \ge x\,} \;\ge\; 3 \cdot \parens{\frac{1}{2}\cdot\frac{n}{5} } \;\approx\; \frac{3n}{10}.
> $$
> 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 thus has at most $\approx 7n/10$ elements. $\qed$

(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 $\ceil{n/5}$ medians, a subproblem of size $n/5$;
- recursing into the surviving side, a subproblem of size at most $7n/10$.

$$
T(n) \le T\!\parens{\frac{n}{5}} + T\!\parens{\frac{7n}{10}} + O(n).
$$

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

$$
% caption: The two recursive calls span $\tfrac15 + \tfrac{7}{10} = \tfrac{9}{10} < 1$ of
%          the input; the leftover $\tfrac{1}{10}$ gap is the shrinkage that forces
%          $O(n)$.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \draw (0,0) rectangle (10,0.7);
  \draw[fill=acc!18] (0,0) rectangle (2,0.7);   \node at (1,0.35) {$\tfrac n5$};
  \draw[fill=acc!32] (2,0) rectangle (9,0.7);    \node at (5.5,0.35) {$\tfrac{7n}{10}$};
  \draw[fill=black!8] (9,0) rectangle (10,0.7);  \node[font=\scriptsize] at (9.5,0.35) {gap};
  \node[anchor=west, font=\scriptsize] at (0,-0.55) {median of $\tfrac n5$ medians};
  \draw[->] (1,-0.35) -- (1,-0.05);
  \node[anchor=east, font=\scriptsize] at (9,-0.55) {surviving side};
  \draw[->] (5.5,-0.35) -- (5.5,-0.05);
\end{tikzpicture}
$$

Start with the single-call cousin
$f(n) \le f(n/2) + bn$. The
[master theorem](/algorithms/foundations/recurrences) gives $f(n) = O(n)$;
unrolling shows why directly,

$$
f(n) \le f\!\parens{\tfrac{n}{2}} + bn
\le f\!\parens{\tfrac{n}{4}} + b\tfrac{n}{2} + bn
\le f(1) + \parens{bn + \tfrac{bn}{2} + \tfrac{bn}{4} + \cdots}
\le f(1) + 2bn.
$$

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, stated as a general lemma:

> **Lemma (Shrinkage).** Suppose $T(n) \le c$ for $n \le n_0$, and
> $T(n) \le T(\lambda n) + T(\mu n) + bn$ for $n > n_0$, where
> $\lambda, \mu, b > 0$ are constants with $\lambda + \mu < 1$. Then
> $T(n) = O(n)$.

> **Proof.** By induction on $n$ we show $T(n) \le an$ for all $n \ge 1$, where
>
> $$
> a = \max\set{\,c,\ \frac{b}{1 - \lambda - \mu}\,}.
> $$
>
> Note $a > 0$ is well-defined precisely because $\lambda + \mu < 1$. The base
> cases $n \le n_0$ hold since $T(n) \le c \le a \le an$. For the inductive step
> $n > n_0$, the choice of $a$ gives $b \le a(1 - \lambda - \mu)$, so
>
> $$
> T(n) \le T(\lambda n) + T(\mu n) + bn
> \le a\lambda n + a\mu n + bn
> = \parens{a(\lambda + \mu) + b}n
> \le \parens{a(\lambda + \mu) + a(1 - \lambda - \mu)}n = an. \qquad\square
> $$

Plugging in $\lambda = \tfrac15$, $\mu = \tfrac{7}{10}$ (so
$\lambda + \mu = \tfrac{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
$\tfrac13 + \tfrac23 = 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

Both algorithms are linear, but they trade off differently.

| | expected time | worst case | pivot cost | in practice |
| --- | --- | --- | --- | --- |
| Randomized quickselect | $O(n)$ | $\Theta(n^2)$ | one random draw | fast; the default |
| Median of medians | $O(n)$ | $O(n)$ | recursive, heavy | slow constant |

The median-of-medians algorithm settled a real question: it proves selection is
_possible_ in worst-case linear time, with no randomness and no probabilistic
escape hatch. But its constant factor is large. Every level does the grouping,
the per-group sort, and a second recursive call just to pick the pivot, so the
hidden constant dwarfs quickselect's. On real inputs **randomized quickselect
is faster** and is the algorithm to reach for.[^skiena-select] Its quadratic
worst case is a theoretical possibility that a random pivot makes vanishingly
unlikely — an adversary who cannot see your coin flips cannot force it.

The deterministic version matters in two places. First, when a hard
worst-case guarantee is mandatory (a real-time deadline, or an adversarial
setting where inputs are chosen to break you). Second, and more commonly, as a
**pivot-selection subroutine for quicksort**: use $\textsc{Select}$ to find the
true median in $O(n)$, partition around it, and every quicksort split is
perfectly balanced, giving a worst-case $\Theta(n\log n)$ sort. The practical
compromise, **introselect**, runs plain quickselect but watches the recursion
depth; if it ever exceeds a threshold (a sign of bad pivots), it switches to
median-of-medians for the rest. That keeps quickselect's speed on ordinary
inputs while capping the worst case at $O(n)$ — the strategy C++'s
`std::nth_element` uses.

## Bonus: Closest Pair of Points

Sorting and selection are not the only classics that fall to divide-and-conquer.
Finding the **closest pair** among $n$ points in the plane beats the
$\Theta(n^2)$ brute force the same way: **split** by the median $x$-coordinate,
**recurse** on each half to get the best distance $\delta$ within each side, and
**combine** by checking only pairs that straddle the dividing line. The combine
looks dangerous — a naive cross-check is $\Theta(n^2)$ — but the same
kind of counting argument as in median-of-medians fixes it: any
straddling pair closer than $\delta$ lies in a width-$2\delta$ **strip**, and a
packing bound shows each strip point need only be compared against a _constant_
number of $y$-neighbours. That makes the combine $O(n)$ and the whole recurrence
$T(n) = 2T(n/2) + O(n) = O(n\log n)$. The full algorithm, the strip-packing
proof, and the pseudocode live in
[Polygons & Proximity](/algorithms/computational-geometry/polygons-and-proximity).

::impl{algo="closest_pair"}

## Selection in practice

Selection is a solved problem in theory — both algorithms are linear — but the
constant factors and the shift to huge or distributed data keep it a live
engineering topic.

**Floyd–Rivest: fewer comparisons than either.** The practical winner is often
neither plain quickselect nor median-of-medians but the **Floyd–Rivest**
algorithm (1975). It samples a small random subset of the array, selects two
pivots from the sample chosen to straddle the target rank $k$ with high
probability, and partitions into three parts so that after one pass the surviving
range is a tiny $O(n^{2/3})$-sized sliver almost certain to contain the answer. It
finds the median in $1.5n + o(n)$ expected comparisons, beating quickselect's
constant and far below median-of-medians', which is why high-performance numeric
libraries reach for it when comparisons are the bottleneck. It is a refinement of
the same "sample to guess a good pivot" idea, pushed to two pivots and a sampled
estimate of where $k$ lands.

**Streaming and approximate selection.** When the data is a stream too large to
store — network packets, sensor readings, query logs — you cannot partition an
array you never hold. Exact selection provably needs $\Omega(n)$ space in one
pass, so practical systems compute _approximate_ quantiles instead. Sketches like
**Greenwald–Khanna** (2001) and the **t-digest** (Dunning, 2019) maintain a small
summary, $O(\tfrac1\varepsilon \log(\varepsilon n))$ space, that answers "the
$k$-th order statistic, within rank error $\varepsilon n$" for any $k$. These
power the percentile latency dashboards ($p_{50}$, $p_{99}$) that every
production service watches; the exact median of a billion requests is neither
needed nor affordable, but a $99.9$th percentile good to a fraction of a percent
is both.

**Parallel and distributed medians.** On a cluster the data is sharded across
machines and no single node sees it all. The **median-of-medians idea reappears**:
each machine computes a local summary or weighted median, a coordinator combines
these into a pivot estimate, and one round of counting how many global elements
fall below the pivot narrows the search — a distributed echo of the sequential
partition-and-recurse. The recurring theme across all three settings is the one
this lesson opened with: selection requires _less_ than sorting, and every regime,
sequential, streaming, or distributed, finds a way to do only the work the answer
needs.[^skiena-select]

## Takeaways

- **Selection** finds the $k$-th smallest element; it needs _less_ than
  sorting, so it can run in $O(n)$.
- $\textsc{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
  $\tfrac{1}{5} + \tfrac{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)$.

[^clrs-select]: **CLRS**, Ch. 9 — Medians and Order Statistics: selecting the $k$-th order statistic in linear time without fully sorting.
[^erickson-qsel]: **Erickson**, _Algorithms_, Ch. 1 — Recursion: quickselect adapting quicksort's partition to recurse into only the side that holds the answer.
[^clrs-mom]: **CLRS**, Ch. 9 — Medians and Order Statistics: the Blum–Floyd–Pratt–Rivest–Tarjan median-of-medians algorithm achieving worst-case $O(n)$ via groups of five.
[^skiena-select]: **Skiena**, _The Algorithm Design Manual_, §4 — Sorting and Searching: randomized quickselect as the practical choice over deterministic median-of-medians.