Median of Medians: selection with no bad pivot

The idea: spend a little to pick a pivot that is never bad

Quickselect finds the k-th smallest element by partitioning around a pivot and keeping one side. It is fast on average, but a bad pivot (the smallest or largest value) keeps m − 1 of m elements, and a run of bad pivots costs O(n²). Median of medians (Blum, Floyd, Pratt, Rivest and Tarjan, 1973, often called BFPRT) picks the pivot so carefully that at least about 3/10 of the elements are on each side, whatever the input. Then each round throws away at least 3/10, and the total work is O(n) in the worst case.

The algorithm, step by step

To select the k-th smallest of a range of m elements (target index t = k − 1):

1. If m ≤ 5, sort the range and read index t.
2. Split the range into ⌈m / 5⌉ groups of 5 (the last group may be shorter).
3. Sort each group and take its median. A group of 5 is constant work: at most 10 comparisons with insertion sort, 6 with a clever scheme.
4. The pivot x is the median of the medians, found by calling the same algorithm on the ⌈m / 5⌉ medians.
5. Partition around x into smaller, equal and larger blocks.
6. If t falls in the equal block, x is the answer. Otherwise keep the one side that holds t and repeat.

select(a, k):                     # k-th smallest, 1-based
    if len(a) <= 5: return sorted(a)[k-1]
    medians = [sorted(g)[(len(g)-1)//2] for g in groups_of_5(a)]
    x = select(medians, (len(medians)+1)//2)   # median of medians
    L = [v for v in a if v < x]; E = [v for v in a if v == x]; G = [v for v in a if v > x]
    if k <= len(L):          return select(L, k)
    if k <= len(L) + len(E): return x
    return select(G, k - len(L) - len(E))

In the canvas the cells really move: from the array into the columns of the grid, down the column as it is sorted, sideways when the columns are ordered by median, and back into the array as the partition. The sample is 25 numbers with k = 13 (the median). Round 1 picks 41 from the medians 41 34 62 45 38 and keeps the 13 larger values; two more rounds narrow them to the answer 45, after 121 comparisons in all. (Demo: median of 25)

Why the pivot is never bad

Order the columns by their median. Half of the medians, including x, are ≤ x, and in each of those columns the two values above the median are smaller still. So the top-left block is ≤ x: about 3 elements from each of half the groups, 3/10 of all. The bottom-right block is ≥ x the same way. Nothing in the top-left can be on the larger side, so the larger side has at most about 7/10 of the elements, and so has the smaller side. The exact bound in CLRS is at least 3n/10 − 6 on each side, so at most 7n/10 + 6 are kept.

For 25 elements that is 8 surely ≤ and 8 surely ≥, so at most 16 are kept. The demo built against the algorithm hits that bound exactly: every value that is not forced to be small is large, and 16 of 25 survive round 1. (Demo: the worst split it allows) Sorted input, which ruins quickselect with a last-element pivot (300 comparisons for k = 1 of 25), splits cleanly here: 12 | 13 | 12 in round 1 and 83 comparisons in all. (Demo: sorted 1 … 25) A short last group still works: its median is its lower median. (Demo: 23 elements) Equal values go into the middle block; if the target index lands there the search stops. (Demo: many duplicates)

Why it is O(n)

One round on n elements costs O(n): sorting n/5 groups of 5, plus n − 1 comparisons for the partition. Then there are two recursive calls, one on the n/5 medians and one on at most 7n/10 kept elements:

T(n) ≤ T(n/5) + T(7n/10) + c·n

The two calls together see n/5 + 7n/10 = 9n/10 elements, less than n. So each level of the recursion does at most 9/10 of the work of the one above, and the total is c·n·(1 + 0.9 + 0.81 + …) = 10·c·n: O(n).

Why groups of 5

group size	sure on each side	recurrence	total
3	2 of 3 in half the groups = n/3	T(n/3) + T(2n/3) + cn	sizes sum to n: O(n log n)
5	3 of 5 in half the groups = 3n/10	T(n/5) + T(7n/10) + cn	9n/10 < n: O(n)
7	4 of 7 in half the groups = 2n/7	T(n/7) + T(5n/7) + cn	6n/7 < n: O(n)

Groups of 3 are too small: the two calls together still cover all n elements, so the work does not shrink per level. Five is the smallest odd size that works; larger groups also work but cost more per group.

In practice

The guarantee has a price. Counting comparisons, median of medians is often several times slower than quickselect with a random pivot on ordinary input, which is why the status line shows both. Real libraries use it as a fallback: introselect (C++ std::nth_element in some libraries, Rust select_nth_unstable) runs quickselect and switches to median of medians if the range stops shrinking fast enough, so the common case is fast and the worst case is still O(n). The same pivot also makes quicksort O(n log n) in the worst case, though in practice heap sort is the usual fallback.

See also Quickselect for the average-case version and its sorted-input worst case, Comparison Sorting for the partition step inside quick sort, Quick Sort vs Merge Sort, and Mean vs Median vs Mode for what a median is for.

What the page leaves out

Inputs are capped at 25 whole numbers from 1 to 99, so there are at most 5 groups and the recursive call on the medians is always a base case (a sort of at most 5); on larger inputs that call is a full median-of-medians run of its own. Groups are sorted with insertion sort, not the 6-comparison median-of-5 network. The partition is shown as a stable three-way split rather than an in-place swap loop. The page also leaves out introselect's switching rule, the Floyd–Rivest sampling algorithm, and the "median of ninthers" and other sampled variants.

References

Blum, Floyd, Pratt, Rivest, Tarjan: Time bounds for selection, JCSS 1973

Median of medians (Wikipedia)

Introselect (Wikipedia)

std::nth_element (cppreference)