Median of medians

Quickselect (SORT-8) finds the k-th smallest value in O(n) time on average, but bad pivots make it O(n²). In 1973 Blum, Floyd, Pratt, Rivest and Tarjan found a way to choose a pivot that is always good enough. It makes selection O(n) in the worst case, and the proof is a short use of the recurrences from lesson 2.

Selection, again

Selection means: given n values and a number k, find the value that would be at position k if the list were sorted (k = 0 is the smallest). The median is the case k = n // 2. Sorting first costs O(n log n). Quickselect does better:

1. Choose a pivot value.
2. Split the values into three groups: smaller than the pivot, equal to it, and larger (a three-way partition, SORT-8).
3. If k falls among the smaller values, repeat on them. If it falls among the equal values, the pivot is the answer. Otherwise repeat on the larger values, with k reduced by the number of values dropped.

Each round costs O(m) on m values. If every pivot dropped only one value, the rounds would cost n + (n − 1) + … + 1, which is O(n²). Step through the “First value” variant of the figure: a sorted list with the first value as pivot does exactly that. A random pivot makes this very unlikely, but not impossible, and a fixed rule such as “the first value” or “the middle value” can always be beaten by a list built against it.

A pivot with a guarantee

The median of medians method chooses the pivot like this:

1. Put the values in groups of 5 (the last group may be shorter).
2. Find the median of each group, by sorting the group: at most 10 comparisons for 5 values.
3. Find the median of those medians by calling select itself on them, with k = the middle position. There are about n/5 medians.
4. Use that value as the pivot for the round.

Step through “Median of medians”.

Why it is linear

There are about n/5 groups. The pivot is the median of their medians, so in at least half of the groups the median is at most the pivot. In each of those groups, the median and the two values below it are at most the pivot: 3 values per group. That is at least 3 × (n/10) = 3n/10 values that are at most the pivot. The same argument gives 3n/10 values that are at least the pivot.

(Exactly: the last group may be short, and the pivot’s own group counts once, so the bound is 3n/10 − 6; this changes nothing below.) Now add up the work of one call on n values:

• sorting the groups and taking their medians: O(n);
• select on the n/5 medians: T(n/5);
• the three-way partition: O(n);
• select on the side that is kept, at most 7n/10 values: T(7n/10).

So T(n) ≤ T(n/5) + T(7n/10) + O(n). This is the first variant of lesson 2’s figure: the two parts add up to 9/10 of n, so each level of the recursion tree does at most 9/10 of the work of the level above, and the total is at most 10 times the top level. So T(n) = O(n), in the worst case.

Selection is therefore easier than sorting. Sorting by comparisons needs about n log₂ n comparisons in the worst case (SORT-5), while selection needs only O(n).

Why groups of five

• Groups of 3: half the groups give 2 values each, so only n/3 values are certain to be on one side. A round can keep 2n/3, and T(n) = T(n/3) + T(2n/3) + O(n). The parts add up to exactly 1, which gives Θ(n log n) (the second variant of lesson 2’s figure). Not linear.
• Groups of 5: 1/5 + 7/10 = 9/10, less than 1. Linear.
• Groups of 7: half the groups give 4 values each, so 2n/7 are dropped and at most 5n/7 kept: 1/7 + 5/7 = 6/7. Also linear. Larger groups cost more to sort but give a smaller recursion.

Five is the smallest odd group size for which the simple argument works. Odd sizes give each group a single middle value.

def median_of_group(g):
    """The middle value of a short list, by insertion sort (SORT-1)."""
    g = list(g)
    for i in range(1, len(g)):
        x = g[i]
        j = i - 1
        while j >= 0 and x < g[j]:     # at most 10 comparisons for 5 values
            g[j + 1] = g[j]
            j -= 1
        g[j + 1] = x
    return g[(len(g) - 1) // 2]

Sorting 5 values by insertion takes at most 10 comparisons. A cleverer order finds the median of 5 with only 6, which lowers the constant but not the O(n).

In practice

The guarantee costs extra comparisons. Counting them, a careful version makes about 8 per value on typical lists, while quickselect with random pivots makes about 3. So libraries use a mix:

• Introselect (Musser, 1997) runs quickselect with a cheap pivot and switches to median of medians only if the list is not shrinking fast enough. It is O(n) in the worst case and fast on typical lists. C++’s std::nth_element and NumPy’s numpy.partition are built on it.
• Python’s standard library has no selection function. statistics.median sorts, and heapq.nsmallest(k + 1, a) is O(n log k) (HEAP-5). For one median of a list that fits in memory, sorted(a)[k] runs in C and is usually fast enough.
• The Floyd–Rivest method (1975) picks its pivots from a small random sample and needs only about n + min(k, n − k) comparisons on average, close to the least possible.