Median-of-Medians and the Deterministic Linear Selection Bound

Quickselect is linear in expectation and quadratic in the worst case, and the worst case is reachable by an adversary who knows the pivot rule. A deterministic linear-time selection algorithm exists, published in 1972 and refined a year later, and its structure is worth understanding even though it is a fallback rather than a primary path in every standard library. The mechanism is a pivot rule that guarantees a constant-fraction split, and the interesting part is why the fraction must be a constant and how small the group size can be before the argument collapses.

The requirement on the pivot

Selection’s recurrence is $T(n) = T(n’) + \Theta(n)$ where $n’$ is the size of the side containing the target. If $n’ \le cn$ for some constant $c < 1$, the recurrence resolves to $\Theta(n)$: $n + cn + c^2 n + \cdots = n/(1-c)$.

So the entire problem is producing a pivot whose rank is guaranteed to lie in a fixed central band. A pivot at rank between $n/4$ and $3n/4$ gives $c \le 3/4$ and a total cost below $4n$. Randomisation achieves that band with high probability; a deterministic rule must achieve it always.

Finding a pivot with a guaranteed rank

The algorithm is recursive in an unusual way: it uses selection to find the pivot for selection.

Split the $n$ elements into $\lfloor n/5 \rfloor$ groups of five, with at most four left over. Sort each group with an insertion sort, which needs seven comparisons in the worst case for five elements, and take each group’s median. There are $m = \lfloor n/5 \rfloor$ such medians. Recursively select the median of those $m$ medians; call it $x$.

Now count how many elements are certainly below $x$ and how many are certainly above. Each group whose median is below $x$ contributes at least three elements below $x$: the group’s median and the two elements smaller than it within the group. There are at least $m/2$ such groups, since $x$ is the median of the medians. So at least $3m/2$ elements are below $x$, and by symmetry at least $3m/2$ are above.

With $m \approx n/5$, that is $3n/10$ below and $3n/10$ above, so $x$‘s rank lies between $3n/10$ and $7n/10$. The side containing the target has size at most $7n/10$, giving $c = 7/10$.

Resolving the recurrence

The recurrence has two recursive calls of different kinds:

$$ T(n) \le T(n/5) + T(7n/10) + O(n) $$

The first is the recursive selection of the median of medians, on $n/5$ elements. The second is the selection on the side containing the target, at most $7n/10$. The $O(n)$ term covers the group sorting, the median extraction, and the partition.

The coefficients sum to $1/5 + 7/10 = 0.9 < 1$, which is the whole proof. Substituting a guess $T(n) \le dn$ gives $0.9dn + an$, which is at most $dn$ whenever $d \ge 10a$. The bound is linear, with a constant of about ten times the per-element cost.

That constant is the reason the algorithm is not used as the primary path. A randomised pivot rule has a smaller expected constant. Median-of-medians needs more comparisons than a single partition pass and considerably more moves, because it sorts groups and then partitions. Its role is as a fallback that converts an expected-linear algorithm into a guaranteed-linear one, exactly as heapsort does for introsort.

Why five and not three

The group size determines both the fraction of elements guaranteed to be on each side and the size of the recursive subproblem. With groups of three, the median of medians has rank between $n/3$ and $2n/3$ by the same counting, so the target side is at most $2n/3$. But the recursive call on the medians is on $n/3$ elements, and the coefficients sum to $1/3 + 2/3 = 1$, which does not contract. The recurrence $T(n) \le T(n/3) + T(2n/3) + O(n)$ resolves to $\Theta(n \log n)$, not $\Theta(n)$.

The gain from larger groups is modest. Groups of seven give $1/7 + 5/7 \approx 0.857$, a better contraction at the cost of more comparisons per group, and five remains the standard choice because the sum is already safely below 1. Five is the smallest odd group size that contracts by this argument.

The takeaway is that the group size is not a free parameter but a value constrained by an inequality that must hold strictly.

The implementation shape

The partition step is the same as quickselect’s; only the pivot choice changes. A version that partitions in place around the chosen pivot:

static void isort(int *a, size_t lo, size_t hi)          /* <= 5 elements */
{
    for (size_t i = lo + 1; i <= hi; i++) {
        int key = a[i]; size_t j = i;
        while (j > lo && a[j - 1] > key) { a[j] = a[j - 1]; j--; }
        a[j] = key;
    }
}
static int select_det(int *a, size_t lo, size_t hi, size_t k);
/* sort each group of five, swap its median into a[lo..lo+m); return m */
static size_t gather_medians(int *a, size_t lo, size_t hi)
{
    size_t m = 0;
    for (size_t g = lo; g <= hi; g += 5) {
        size_t end = (g + 4 < hi) ? g + 4 : hi;
        isort(a, g, end);
        size_t mid = g + (end - g) / 2;
        int t = a[lo + m]; a[lo + m] = a[mid]; a[mid] = t;
        m++;
    }
    return m;
}
static int select_det(int *a, size_t lo, size_t hi, size_t k)
{
    while (hi - lo > 4) {
        size_t m = gather_medians(a, lo, hi);
        /* medians sit in a[lo..lo+m); the median of medians is its middle */
        int pivot = select_det(a, lo, lo + m - 1, lo + m / 2);
        size_t lt = lo, i = lo, gt = hi;
        /* lt and gt delimit the equal region; k inside it is the answer */
        while (i <= gt) {                    /* three-way partition by value */
            if (a[i] < pivot)      { int t = a[lt]; a[lt] = a[i]; a[i] = t; lt++; i++; }
            else if (a[i] > pivot) { int t = a[i]; a[i] = a[gt]; a[gt] = t; gt--; }
            else                   i++;
        }
        /* the left part lies wholly in a[lo..lt), so k - lo elements precede k */
        if (k < lt)      hi = lt - 1;
        else if (k > gt) lo = gt + 1;
        else             return pivot;
    }
    isort(a, lo, hi);
    return a[k];
}

gather_medians allocates nothing: each group’s median is swapped into a prefix of the same range, and the recursive call selects among that prefix. That keeps the algorithm in place and gives it $O(1)$ extra space apart from the stack, whose depth is $O(\log n)$ because the recursion on the medians is on a fifth of the range and the partition on the target side reduces the range by at least a factor of $10/7$.

The one subtlety in the code is that k is an index into a, not a rank within the current range. Two facts keep it valid. A group’s median is a prefix position, so when the pivot has been found the left part of the partition is a subset of that prefix, and k’s relation to it is decided by comparing against lt. When the equal region is discarded, gt is short of hi by exactly the count of elements that were known to exceed the pivot, so the right part is the one containing k. Getting either fact wrong produces an on-average-fast function that fails on specific inputs.

Sorting each group of five is where most of the constant lives. A sorting network for five elements uses nine comparisons, while the insertion sort in isort can use up to seven. Since the groups are contiguous, the access pattern is sequential and cache-friendly, which partly offsets the comparison count.

The wider lesson: deterministic guarantees and their price

Median-of-medians establishes that linear-time selection needs no randomness, which matters when the input can be chosen by an adversary: a hash-table implementation defending against collision attacks, a scheduler whose input order is controlled by a client, a system whose timing must be bounded rather than probabilistic.

The price is a constant that makes the algorithm a fallback rather than a first choice, and the pattern repeats across algorithm engineering. Deterministic guarantees cost constants; randomised algorithms achieve better constants with a failure probability that is negligible for fixed input but not for adversarial input. The engineering resolution is usually a hybrid: randomised fast path with a deterministic fallback triggered by a counter, which is the structure of introsort and of its selection analogue.

A second lesson is that the group size is a design parameter with a discrete constraint. The recurrence contracts or it does not, and the threshold is a specific rational inequality. That kind of constraint is common in divide-and-conquer analysis and rare in the prose descriptions of algorithms, which tend to present the chosen parameter as given.

What the bound does not promise

Linear time here means linear comparisons and linear moves, with a constant near ten times the per-element cost of a single pass. The algorithm is linear in the same sense that a majority-vote scan is linear; the asymptotics are the same and the practical costs are not.

The bound also assumes a comparison model with unit-cost comparisons. If comparisons are expensive and the keys are structured, a different approach entirely may be better: sorting by radix gives linear time with a much smaller constant on integer keys, and histogram-based selection over a small key domain gives linear time with no recursion at all. Median-of-medians matters most for abstract comparable keys where no such structure is available.