15.13 Median of Medians

Problem

Quickselect finds the (k)-th smallest element in expected linear time.

In practice, this is often sufficient. Random pivots work well, and the probability of repeatedly choosing poor pivots is low.

However, some applications require stronger guarantees.

Examples include:

• real-time systems
• adversarial inputs
• security-sensitive software
• theoretical algorithm analysis
• worst-case performance guarantees

Can we design a selection algorithm that always runs in linear time, regardless of the input?

Solution

Use the Median of Medians algorithm.

The algorithm was introduced by entity["people","Manuel Blum","computer scientist"], entity["people","Robert Floyd","computer scientist"], entity["people","Vaughan Pratt","computer scientist"], entity["people","Ronald Rivest","computer scientist"], and entity["people","Robert Tarjan","computer scientist"] in 1973.

Its purpose is not to make selection faster in practice. Its purpose is to guarantee a good pivot.

The algorithm chooses a pivot that is provably close to the true median, ensuring that each recursive step discards a constant fraction of the remaining elements.

As a result, selection runs in:

$$ O(n) $$

worst-case time.

Why Quickselect Can Fail

Consider a sorted array:

[1,2,3,4,5,6,7,8,9]

If the first element is repeatedly chosen as pivot:

1

then:

left side  = empty
right side = all remaining elements

The recurrence becomes:

$$ T(n)=T(n-1)+O(n) $$

which yields:

$$ O(n^2) $$

Randomization makes this unlikely, but not impossible.

Median of medians removes that possibility entirely.

High-Level Idea

The algorithm proceeds in five stages:

1. Divide the input into groups of five.
2. Find the median of each group.
3. Collect those medians.
4. Recursively find the median of the medians.
5. Use that value as the pivot.

The resulting pivot is guaranteed to be reasonably central.

Not perfectly central.

Just central enough.

That is all the algorithm needs.

Step 1: Form Groups of Five

Suppose we have:

[9, 1, 7, 4, 3,
 8, 2, 6, 5, 0,
 12,11,10]

Divide into groups:

[9,1,7,4,3]
[8,2,6,5,0]
[12,11,10]

Groups near the end may contain fewer than five elements.

That does not affect correctness.

Step 2: Find Each Median

Sort each small group.

[1,3,4,7,9]
median = 4

[0,2,5,6,8]
median = 5

[10,11,12]
median = 11

Collect:

[4,5,11]

These values summarize the larger input.

Step 3: Recursively Find Their Median

Find the median of:

[4,5,11]

which is:

5

This becomes the pivot.

Notice what happened.

Instead of choosing a random element, we selected a value that reflects the structure of the entire array.

Why Groups of Five?

The choice seems arbitrary.

Why not:

3?
7?
11?

Groups of five provide a balance.

They are:

• small enough to sort efficiently
• large enough to guarantee progress

Smaller groups weaken the guarantee.

Larger groups increase constant factors.

Five is the smallest group size that yields the classical linear-time proof.

The Key Guarantee

Let:

pivot = median of medians

At least half of the group medians are greater than or equal to the pivot.

Each such median is greater than or equal to two elements in its group.

Therefore a large fraction of the entire array is guaranteed to be:

>= pivot

A symmetric argument holds for elements:

<= pivot

The result:

At least:

$$ \frac{3n}{10} $$

elements lie on each side of the pivot.

Therefore no recursive call contains more than:

$$ \frac{7n}{10} $$

elements.

This constant-factor reduction is enough to guarantee linear time.

Visualizing the Guarantee

Imagine:

all elements

divided into groups:

[.....]
[.....]
[.....]
[.....]
...

The median-of-medians sits near the middle of the group medians.

That automatically places many entire groups on either side.

Those groups contribute multiple elements that can be discarded immediately.

The algorithm does not find a perfect median.

It finds a pivot that is guaranteed to eliminate enough work.

Recursive Structure

The algorithm performs:

1. Find medians of groups.
2. Recursively find the median of medians.
3. Partition around that pivot.
4. Recurse into one side.

Pseudo-code:

select(A, k)

    divide into groups of 5

    find group medians

    pivot =
        select(medians, middle)

    partition around pivot

    recurse into one side

The structure resembles Quickselect.

The difference is pivot selection.

Recurrence Analysis

The recursive calls are:

1. Find the median of medians:

$$ T(n/5) $$

2. Recurse into the larger partition:

$$ T(7n/10) $$

3. Group processing and partitioning:

$$ O(n) $$

The recurrence becomes:

$$ T(n) = T(n/5) + T(7n/10) + O(n) $$

This solves to:

$$ O(n) $$

The proof is more involved than the Master Theorem because the subproblem sizes differ.

The important result is that the total work remains linear.

Implementation Sketch

A production implementation is lengthy because of partition management.

The essential structure looks like:

func Select(nums []int, k int) int {
    if len(nums) <= 5 {
        sort.Ints(nums)
        return nums[k]
    }

    medians := collectMedians(nums)

    pivot := Select(
        medians,
        len(medians)/2,
    )

    pos := partitionAroundValue(
        nums,
        pivot,
    )

    switch {
    case k < pos:
        return Select(nums[:pos], k)

    case k > pos:
        return Select(
            nums[pos+1:],
            k-pos-1,
        )

    default:
        return nums[pos]
    }
}

Real implementations must handle duplicates carefully.

Comparing Quickselect and Median of Medians

Property	Quickselect	Median of Medians
Average Time	(O(n))	(O(n))
Worst Case	(O(n^2))	(O(n))
Simplicity	Excellent	Complex
Constant Factor	Small	Large
Practical Performance	Usually Faster	Usually Slower

This table explains why most libraries do not use median of medians directly.

The theoretical guarantee is stronger.

The practical performance is often worse.

Introselect

Many production systems combine both ideas.

The algorithm begins with Quickselect.

If recursion depth becomes suspiciously large:

too many bad pivots

it switches to median of medians.

This hybrid approach is called Introselect.

The philosophy mirrors Introsort:

• fast average case
• guaranteed worst case

Many standard libraries use some variation of this strategy.

Applications

Median of medians appears in:

Order Statistics

Finding:

• median
• quartiles
• percentiles
• arbitrary ranks

Robust Algorithms

Algorithms that must maintain predictable worst-case performance.

Computational Geometry

Many geometric algorithms depend on reliable selection routines.

Theoretical Computer Science

The algorithm is one of the classic examples of worst-case linear time.

Common Mistakes

Sorting the Entire Array

The algorithm only sorts groups of five.

Sorting everything defeats the purpose.

Using the Wrong Median

The pivot must be the median of the medians.

Using the average or a random median breaks the guarantee.

Ignoring Duplicates

Many textbook implementations assume distinct values.

Real data often contains duplicates.

Partitioning must handle them correctly.

Expecting Practical Speedups

Median of medians improves worst-case complexity.

It does not necessarily improve wall-clock time.

For many workloads, randomized Quickselect remains faster.

Misunderstanding the Goal

The algorithm is not trying to find the exact median immediately.

It is trying to find a pivot that guarantees sufficient progress.

That distinction is essential.

Discussion

Median of medians is one of the most celebrated examples of divide-and-conquer analysis. The algorithm succeeds not because it finds a perfect pivot, but because it finds a pivot that is good enough. A constant fraction of the input is eliminated on every recursive step, and that guarantee is all the complexity proof requires.

This is an important lesson in algorithm design. Optimal decisions are often unnecessary. A decision that is consistently good can be more valuable than a decision that is occasionally perfect. Median of medians trades simplicity and practical speed for a mathematical guarantee, demonstrating how carefully structured recursion can transform a probabilistic algorithm into a deterministic one.

The next section returns to a more practical divide-and-conquer application: counting inversions. Unlike selection, where the goal is to find a single element, inversion counting extracts global information about the ordering of an entire array while preserving the efficiency of merge sort.