Selection in Linear Time

The question

Here are fifteen numbers:

Which one is the median? That is the 8th smallest, which sits at index $k=7$ once the array is sorted (this course writes ranks as 0-indexed $k$ in code and says "the $(k+1)$-th smallest" in prose). The answer is 58. The real question of this module is how much work it takes to know that.

The selection problem: given $n$ elements and a rank $k\in \{0,\dots ,n-1\}$, return the element that would be at index $k$ after sorting. The median is $k=\lfloor (n-1)/2\rfloor$.

The naive approach, and where it wastes work

Sort, then index. With a good comparison sort that costs $\Theta (n\log n)$ comparisons, and module 02 proves no comparison sort can do better.

The waste is visible once you look at what sorting computes. After sorting $A$ you know that $58<59$, that $93<97$, that $4<23$: the exact rank of all fifteen elements. You asked for one. The question is whether one rank is genuinely cheaper than all fifteen.

The model: count comparisons

In the comparison model the elements are opaque. The only thing an algorithm may do with two of them is ask "is $x<y$?", and its cost is the number of such questions. This model is the right one when the elements could be any comparable type, and it is what makes lower bounds provable in module 02. The lab counts comparisons for you with CountingList.

One partition, one part kept

Pick any element $p$ as a pivot and split the array in one pass into three parts:

• less: the elements smaller than $p$
• equal: the elements equal to $p$
• greater: the elements larger than $p$

Every element of less is smaller than every element of equal, which is smaller than every element of greater. So the rank-$k$ element is:

• the rank-$k$ element of less, if $k<|less|$;
• $p$ itself, if $|less|\le k<|less|+|equal|$;
• otherwise the rank-$(k-|less|-|equal|)$ element of greater.

Why three parts and not two? With duplicates, a two-way split (< p and >= p) can keep an array unchanged forever: split [5, 5, 5, 5, 5, 5, 5] at 5 and the kept part is the whole array again.

Everything now depends on the pivot. A pivot near the middle throws away about half the array. A pivot at the extreme throws away one element.

Median of medians, traced on $A$

The deterministic way to guarantee a good pivot (Blum, Floyd, Pratt, Rivest and Tarjan, 1973):

1. Split the array into groups of 5 and find each group's median (sorting 5 elements is cheap).
2. Recursively select the median of those $\lceil n/5\rceil$ medians. Call it $p$.
3. Partition around $p$ and keep the part that contains rank $k$.

Here it is on $A$ with $k=7$:

In round 2 the pivot 27 has 3 elements below it and 1 equal to it, so the answer's rank inside greater is $7-3-1=3$.

Why the pivot is good

Line the groups up as columns, ordered by their medians. At least half of the group medians are $\le p$. Each of those groups has 3 elements $\le$ its own median, and so $\le p$. Leave out the possibly short last group, the only one that can have fewer than 3. Textbooks also leave out $p$'s own group, because they count the elements strictly less than $p$. Counting $\le p$ we don't need to, so the $-6$ below is a safe overcount. At least

$$3(\lceil \frac{1}{2}\lceil \frac{n}{5}\rceil \rceil -2)\ge \frac{3n}{10}-6$$

elements are $\le p$. By the symmetric argument, as many are $\ge p$. So whichever part we keep has at most $\frac{7n}{10}+6$ elements.

The recurrence

Let $T(n)$ be the worst-case number of comparisons. Finding the group medians and partitioning cost at most $cn$. The recursive call on the $\lceil n/5\rceil$ medians costs $T(\lceil n/5\rceil )$, and the call on the kept part costs at most $T(7n/10+6)$:

$$T(n)\le T\left(\lceil \frac{n}{5}\rceil \right)+T(\frac{7n}{10}+6)+cn.$$

Ignoring the rounding and the $+6$, the sizes on each level shrink by the factor $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}$, so the total work is a geometric series:

$$T(n)\le cn(1+0.9+{0.9}^2+\cdots )=10cn.$$

Keeping the rounding and the $+6$ costs a little more, but the total stays linear (the section on measuring works out the exact constant for real code). Median of medians selects in $O(n)$ comparisons in the worst case.

One step here is easy to skip, and it is the whole reason the argument works: the two fractions must add up to strictly less than 1. With groups of 3, the pivot is only guaranteed about $n/3$ elements on each side, and the recurrence becomes $T(n)\le T(n/3)+T(2n/3)+cn$. Its fractions sum to 1, every level of its tree sums to the full $cn$, and there are $\Theta (\log n)$ levels. So this analysis no longer proves linear time: it only gives $O(n\log n)$. That is a failure of the proof, not a proof that the algorithm is slow; Chen and Dumitrescu (2015) give cleverer variants with groups of 3 or 4 that do run in linear time. Groups of 7 keep the simple argument working, since $\frac{1}{7}+\frac{5}{7}<1$.

Letting the coins choose: quickselect

There is a much simpler way to get a good pivot: pick one uniformly at random.

import random

def partition3(a, p):
    return ([x for x in a if x < p], [x for x in a if x == p], [x for x in a if x > p])

def quickselect(a, k, rng):
    while len(a) > 1:
        p = rng.choice(a)
        less, equal, greater = partition3(a, p)
        if k < len(less):
            a = less
        elif k < len(less) + len(equal):
            return p
        else:
            k -= len(less) + len(equal)
            a = greater
    return a[0]

A = [31, 4, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27]
assert all(quickselect(A, k, random.Random(seed)) == sorted(A)[k]
           for k in range(15) for seed in range(5))

Call a pivot good if its rank lies in the middle half of the current array. A good pivot leaves at most $3/4$ of the array, and a random pivot is good with probability at least $1/2$. So it takes an expected 2 rounds at most to shrink the array by a factor of $3/4$. Each of those rounds costs time linear in the current size, and summing the geometric series over the shrinking sizes gives expected $O(n)$ comparisons.

Read that guarantee precisely. The expectation is over the algorithm's own coin flips, and it holds for every input, sorted ones included. It is not a statement about "random inputs". The worst case is still $\Theta (n^2)$: every pivot could, by bad luck, be the maximum. An adversary cannot arrange that, because the adversary does not see the coins.

Measure the claim

A bound claims how the cost grows. Divide the measured cost by $n$: if the ratio is flat, the cost is linear. Comparisons per element, on seeded random arrays:

Median of medians stays flat near 10. The measured code sorts each group of 5 by insertion (at most 10 comparisons per group) and partitions with at most 2 comparisons per value (x < p, then x > p), so one round costs at most $4n$ and $c=4$. The recursion tree then promises $40n$, but only once the rounding and the $+6$ are ignored. With them kept, iterate the recurrence exactly:

from math import ceil

def worst_case(N):
    """The bound T(n) for n = 0..N, with the rounding and the +6 kept."""
    T = [n * (n - 1) // 2 for n in range(6)]   # insertion sort, n <= 5
    most = list(T)             # most[n] = max(T[0..n]): a bound for "at most n"
    for n in range(6, N + 1):
        g = ceil(n / 5)                        # groups, so medians
        kept = min(n - 1, n - 3 * (ceil(g / 2) - 2))
        r = n % 5                              # size of a short last group
        one_round = 10 * (n // 5) + r * (r - 1) // 2 + 2 * n
        assert one_round <= 4 * n and kept <= 7 * n / 10 + 6
        T.append(one_round + most[g] + most[kept])
        most.append(max(most[-1], T[-1]))
    return T

T = worst_case(20_000)
peak = max(range(1, 20_001), key=lambda n: T[n] / n)
assert peak == 136 and 43.3 < T[136] / 136 < 43.4       # 43.35n
assert 41.3 < T[20_000] / 20_000 < 41.4                 # still falling
# Above 20,000, assume T(m) <= 44m for smaller m and substitute:
# 4n + 44(n/5 + 1) + 44(7n/10 + 6) = 43.6n + 308 <= 44n once n >= 770.
assert all(43.6 * n + 308 <= 44 * n for n in range(770, 20_001))

So the worst case is never more than $44n$ (its peak is $43.35n$, at $n=136$) and about $40n$ for large $n$ ($41.3n$ at $n$ = 20,000, still falling). Random input sits far below that bound. Quickselect is about twice as cheap. Merge sort's ratio keeps climbing, because it grows like $\log n$.

Median of medians loses to quickselect by a constant factor, which is why libraries start with cheap pivots and keep a fallback for when the recursion goes too deep. NumPy's np.partition (default kind='introselect') picks deterministic median-of-3 pivots and switches to median of medians after about $2{\log }_{2}n$ rounds, so that routine is worst-case linear. (On recent x86 CPUs a single k on a plain numeric array goes to a vectorized quickselect instead, whose fallback is sorting.) GCC's std::nth_element also uses median-of-3 pivots but falls back to heap selection, which is $O(n\log n)$. Neither flips coins, so neither is the random-pivot quickselect above.

A problem that looks different

A post office will be built on a straight road with houses at positions 2, 5 and 9. Where should it go to minimize the total walking distance of the residents? Nothing in the question says "median". Before reading on, ask yourself why it might still be one. The lab's last exercise is a different problem of the same kind, and it will not tell you which technique to use either.

Practise

The lab runs in your browser and draws your own code's state as it runs: an in-place partition whose regions you watch grow, a round-by-round trace of median of medians on a new array, the algorithm itself, a measurement of your comparisons against sorting, and one problem that does not say what it is.

Recap

• You can now: reduce selection to a three-way partition; prove quickselect's expected $O(n)$; prove median of medians linear in the worst case from its recurrence; and spot a selection problem that never says "median".
• Invariant: the answer is the rank-$k$ element of the part you hold, with $k$ shifted by the sizes of the parts discarded to its left.
• Complexity achieved: $O(n)$, expected or worst case, against $\Theta (n\log n)$ for sorting.
• Failure mode: a two-way partition on an array with duplicates, which loops forever or returns the wrong rank.
• In real software: NumPy's np.partition and GCC's std::nth_element both start with median-of-3 pivots; NumPy falls back to median of medians (worst-case linear), GCC to heap selection ($O(n\log n)$). The C++ standard only asks for linear time on average.
• Next: module 02 proves lower bounds. No comparison sort beats $n\log n$, and even the median needs at least about $3n/2$ comparisons.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. Why does the median of medians have many elements on both sides, and where does the $-6$ come from?
2. With groups of 3 instead of 5, what does the recursion-tree argument give, and why is that not a proof that the algorithm is slower?
3. On a sorted array of a million elements, compare quickselect with a first-element pivot, quickselect with a random pivot, and median of medians.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.