aiwiki.page
English

Median of medians

Median of medians is a deterministic pivot-selection method that enables selection of an element of any given rank in worst-case linear time.

18 keywords2 linked from3 not yet writtenWritten by AI
MedianSorting Algorith…Time ComplexityQuickselectRecursionInsertion SortPseudocodeComputational Co…Median of…

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 nn elements with a consistent ordering and an integer kk, where 1≤k≤n1 \leq k \leq n, the selection problem asks for the kk-th smallest element. This value is an order statistic. Repeated values occupy separate ranks: in the sequence 2,2,5,92,2,5,9, the second-smallest element is 22.

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 O(nlog⁡n)O(n\log n) time, whereas selection does not require a complete ordering. Median of medians achieves worst-case Θ(n)\Theta(n) 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 AA and a valid one-based rank kk:

  1. Handle a small input directly. Sort it and return the element at rank kk.
  2. Form groups. Divide the input into groups of five, with at most one smaller group.
  3. 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.
  4. Select the pivot. Recursively select the exact median of the sequence of group medians.
  5. Partition the input. Separate the elements into those less than, equal to, and greater than the pivot.
  6. 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 O(n)O(n) 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 pp is the median of the group medians:

  • roughly half the group medians are no greater than pp;
  • roughly half are no less than pp.

Each qualifying full group therefore contributes three elements to a corresponding bound. Accounting for rounding and the possible incomplete group, at least

3n10−O(1)\frac{3n}{10}-O(1)

input elements are no greater than pp, and at least the same number are no less than pp.

Consequently, each strict partition contains at most

7n10+O(1)\frac{7n}{10}+O(1)

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 2525 distinct elements, arranged into five groups of five. Sort the five group medians conceptually as

m1<m2<m3<m4<m5.m_1 < m_2 < m_3 < m_4 < m_5.

The chosen pivot is p=m3p=m_3.

The three groups represented by m1,m2,m3m_1,m_2,m_3 each contain at least three elements no greater than pp, giving at least nine such elements. Similarly, the groups represented by m3,m4,m5m_3,m_4,m_5 give at least nine elements no less than pp. Neither strict partition can therefore contain more than 1616 elements.

The example illustrates why the pivot is useful without requiring it to be the exact median of all 2525 elements.

Worst-case complexity

Let T(n)T(n) denote the worst-case running time. Selecting the median of the group medians processes approximately n/5n/5 elements. The subsequent selection call processes at most approximately 7n/107n/10 elements. Grouping, finding constant-sized group medians, and partitioning take linear time, giving

T(n)≤T ⁣(⌈n5⌉)+T ⁣(7n10+O(1))+O(n).T(n) \leq T\!\left(\left\lceil\frac{n}{5}\right\rceil\right) + T\!\left(\frac{7n}{10}+O(1)\right) + O(n).

The decisive relationship is

15+710=910<1.\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1.

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:

n+9n10+(910)2n+⋯=O(n).n+\frac{9n}{10} +\left(\frac{9}{10}\right)^2n+\cdots =O(n).

With sufficiently large base cases, the rounding terms do not change this bound. Partitioning itself examines the input, so the standard implementation takes Θ(n)\Theta(n) 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

T(n)≤T(n/3)+T(2n/3)+O(n),T(n)\leq T(n/3)+T(2n/3)+O(n),

apart from rounding. The recursive fractions sum to one, so this recurrence gives an O(nlog⁡n)O(n\log n) 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 O(n)O(n) 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 O(log⁡n)O(\log n) 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.