Median of Medians

Median of Medians is a pivot selection method for deterministic linear-time selection. It chooses a pivot that is good enough to discard a constant fraction of the input after partitioning.

The method is most often used inside Deterministic Select. It gives worst-case guarantees, but it has larger constant factors than randomized pivot selection.

Problem

Given an array $A$, choose a pivot value that is close enough to the true median to support guaranteed progress in selection.

Algorithm

Split the input into groups of five. Sort each small group and take its median. Recursively find the median of those medians.

median_of_medians(A):
    if length(A) <= 5:
        sort A
        return A[length(A) // 2]

    groups = split A into groups of 5
    medians = empty list

    for each group in groups:
        sort group
        append group[length(group) // 2] to medians

    return median_of_medians(medians)

Key Idea

Each group median is greater than at least two elements in its group and less than at least two elements in its group. Because the chosen pivot is the median of these medians, many group medians lie below it and many lie above it.

This means a fixed fraction of the original array is known to be smaller than the pivot, and a fixed fraction is known to be larger.

Guarantee

For groups of five, at least about $3n/10$ elements are less than or equal to the pivot, and at least about $3n/10$ elements are greater than or equal to it.

Therefore the largest recursive selection side has size at most about:

This gives the standard selection recurrence:

which solves to:

Correctness

The algorithm returns an element from the input. The grouping and recursive median step only determine which pivot to choose. Once the pivot is used in partitioning, the ordinary rank argument for selection applies.

The pivot need not be the true median. It only needs to be sufficiently central to guarantee that many elements can be discarded.

Complexity

Space is $O(n)$ in the simple list-building version and can be reduced with in-place grouping.

When to Use

Use Median of Medians when worst-case linear selection matters more than implementation simplicity or constant factors.

It is mainly useful in theory, adversarial settings, real-time systems, and as a fallback inside hybrid algorithms.

Implementation

def median_of_medians(a):
    if len(a) <= 5:
        return sorted(a)[len(a) // 2]

    medians = []

    for i in range(0, len(a), 5):
        group = a[i:i + 5]
        group.sort()
        medians.append(group[len(group) // 2])

    return median_of_medians(medians)

func MedianOfMedians(a []int) int {
	if len(a) <= 5 {
		tmp := append([]int(nil), a...)
		sortInts(tmp)
		return tmp[len(tmp)/2]
	}

	medians := make([]int, 0, (len(a)+4)/5)

	for i := 0; i < len(a); i += 5 {
		end := i + 5
		if end > len(a) {
			end = len(a)
		}

		group := append([]int(nil), a[i:end]...)
		sortInts(group)
		medians = append(medians, group[len(group)/2])
	}

	return MedianOfMedians(medians)
}