Median of medians is a deterministic method for choosing a pivot in a selection algorithm, allowing the element of any specified rank to be found in worst-case linear time. Its standard form divides the input into groups of five, finds each group's median, and recursively selects the exact median of those medians. This pivot need not be the median of the original input, but it guarantees that a fixed fraction of the elements can be discarded at each selection step. The method is commonly associated with the BFPRT algorithm, named after Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan.
The selection problem
Given elements with a consistent ordering and an integer , where , the selection problem asks for the -th smallest element. This value is an order statistic. Repeated values occupy separate ranks: in the sequence , the second-smallest element is .
Selection includes finding a minimum, a maximum, or a median. For an even number of numerical values, a statistical median is often defined as the arithmetic mean of the two central order statistics; a selection algorithm returns either central element directly, and both can be obtained if their mean is required.
One approach is to sort the entire input and then retrieve the requested position. A comparison-based sorting algorithm generally takes time, whereas selection does not require a complete ordering. Median of medians achieves worst-case time complexity under the usual assumption that comparisons and element operations take constant time.
Algorithm
Median of medians supplies a pivot for a partition-based selection procedure closely related to Quickselect. The procedure uses recursion in two places: to select a pivot from the group medians, and to continue searching the relevant partition of the original input.
For a nonempty input sequence and a valid one-based rank :
- Handle a small input directly. Sort it and return the element at rank .
- Form groups. Divide the input into groups of five, with at most one smaller group.
- Find the group medians. Sort each group and extract its middle element. For an even-sized final group, either central element can be used consistently.
- Select the pivot. Recursively select the exact median of the sequence of group medians.
- Partition the input. Separate the elements into those less than, equal to, and greater than the pivot.
- Continue only where necessary. Return the pivot if the requested rank falls in its equal partition; otherwise recurse on the appropriate strict partition with an adjusted rank.
The group size is fixed, so sorting every group costs only time in total. A simple method such as insertion sort is sufficient for these tiny groups.
Pseudocode
The following pseudocode uses one-based ranks and chooses the lower median when a sequence has even length:
SELECT(A, k):
require 1 <= k <= length(A)
if length(A) <= 5:
sort A
return A[k]
M = empty sequence
for each consecutive group G of at most 5 elements in A:
sort G
append G[ceil(length(G) / 2)] to M
p = SELECT(M, ceil(length(M) / 2))
L = elements of A strictly less than p
E = elements of A equal to p
R = elements of A strictly greater than p
if k <= length(L):
return SELECT(L, k)
if k <= length(L) + length(E):
return p
return SELECT(R, k - length(L) - length(E))
Three-way partitioning is important for repeated values. If all input elements equal the pivot, the algorithm terminates immediately after partitioning. An implementation that sends equal elements into a recursive branch without controlling its size can lose the intended worst-case guarantee.
Why the pivot is sufficiently balanced
Consider the full groups of five. Each group median has at least three elements in its group that are no greater than it, and at least three that are no less than it, counting the median itself.
Because the pivot is the median of the group medians:
- roughly half the group medians are no greater than ;
- roughly half are no less than .
Each qualifying full group therefore contributes three elements to a corresponding bound. Accounting for rounding and the possible incomplete group, at least
input elements are no greater than , and at least the same number are no less than .
Consequently, each strict partition contains at most
elements. Once the input has been partitioned, selection can discard approximately 30 percent of it even in the least favorable case.
For distinct elements, this is often described as choosing a pivot between approximately the 30th and 70th percentiles. With duplicates, the non-strict counting argument and the sizes of the strict partitions are the more precise statements.
An illustrative case
Suppose there are distinct elements, arranged into five groups of five. Sort the five group medians conceptually as
The chosen pivot is .
The three groups represented by each contain at least three elements no greater than , giving at least nine such elements. Similarly, the groups represented by give at least nine elements no less than . Neither strict partition can therefore contain more than elements.
The example illustrates why the pivot is useful without requiring it to be the exact median of all elements.
Worst-case complexity
Let denote the worst-case running time. Selecting the median of the group medians processes approximately elements. The subsequent selection call processes at most approximately elements. Grouping, finding constant-sized group medians, and partitioning take linear time, giving
The decisive relationship is
Ignoring bounded rounding effects, the total size of the recursive subproblems contracts by a fixed factor. The resulting work is bounded by a geometric series:
With sufficiently large base cases, the rounding terms do not change this bound. Partitioning itself examines the input, so the standard implementation takes worst-case time. This matches the asymptotic worst-case lower bound for general comparison-based selection.
Why groups of five?
Five is a small odd group size for which the straightforward analysis yields a strict contraction.
With groups of three, the analogous basic estimate is
apart from rounding. The recursive fractions sum to one, so this recurrence gives an upper bound rather than establishing linear time. This does not show that all algorithms using groups of three require superlinear time: modified grouping strategies can obtain stronger guarantees.
Larger fixed odd groups, such as seven or nine, also permit linear-time selection through the same general argument. Their practical costs depend on how group medians are computed and on implementation details.
Historical significance
Blum, Floyd, Pratt, Rivest, and Tarjan published their selection result in the 1973 paper Time Bounds for Selection. Their algorithm, called PICK, established deterministic worst-case linear-time selection.
The result was important in computational complexity because it showed that finding a median does not require sorting the input. Selection and sorting have different information requirements: a selected order statistic can be identified without determining the relative order of every pair of elements.
Modern presentations commonly use the simpler groups-of-five formulation to explain the BFPRT result. The original paper included a more detailed analysis of comparison counts; the standard textbook procedure should not be assumed to reproduce all of its constants.
Relationship to other algorithms
Quickselect
Quickselect partitions around a pivot and continues in only one partition. With a uniformly randomized pivot, it has expected linear running time, but its worst-case running time is quadratic.
Median of medians replaces this probabilistic balance with a deterministic size guarantee. It needs neither random sampling nor an assumption about the input's initial arrangement. The trade-off is additional work to construct a guaranteed pivot. In practice, a randomized algorithm or a simple pivot-selection heuristic may be faster on ordinary inputs.
Median-of-three pivot selection
Median of medians is not the same as median-of-three, a common pivot heuristic in Quicksort. Median-of-three selects the median of three sampled elements, often the first, middle, and last elements of a range. Those samples alone do not guarantee that a fixed fraction of the entire range lies on either side.
Likewise, repeatedly taking medians of small groups until only one representative remains is not automatically the standard median-of-medians algorithm. The essential step in the standard method is to select the exact median of the complete sequence of group medians.
Introselect and hybrid methods
Introselect combines a fast selection procedure with a fallback intended to prevent pathological behavior. Median of medians can serve as a linear-time fallback.
The fallback alone does not establish a linear bound for the whole hybrid. The trigger must also limit work performed before switching: allowing many nearly full-size partitioning passes can accumulate superlinear work before the fallback begins.
Implementation and applications
The pseudocode above allocates separate sequences for the group medians and partitions, giving a straightforward implementation with auxiliary space complexity. Implementations based on an array can rearrange elements in place, move group medians into a prefix, and partition without full-sized auxiliary arrays. A straightforward recursive in-place implementation uses call-stack space.
Median of medians is useful when worst-case selection guarantees matter, including exact quantile computation, partitioning around a specified rank, and algorithms in computational geometry that require balanced splits. It also provides a standard example of divide-and-conquer analysis with unequal recursive subproblem sizes.
Its principal practical limitation is overhead: repeated group processing and recursive pivot selection can cost more than simpler pivot strategies. Its linear-time bound also concerns the number of elementary operations under a specified computation model. Expensive comparisons, large records, and memory-access costs can materially affect actual running time without changing the asymptotic comparison-based guarantee.