View source for Median of medians

{{Short description|Fast approximate median algorithm}}
{{More footnotes|date=June 2020}}{{Infobox Algorithm
|name=Median of Medians
|alt = Illustration showing vertical rectangles with 5 circles in each. The middle circle is black and the others are white/empty. The very middle rectangle has an arrow pointing to its black circle and an 'x' at the end of the arrow.
|caption = Median of medians
|class=[[Selection algorithm]]
|image=Median_Of_Medians_-_Color.png
|data=[[Array data structure|Array]]
|best-time= <math>O(n)</math>
|time=<math>O(n)</math>
|space=<math>O(\log n)</math> auxiliary
|optimal=Yes
}}

In [[computer science]], the '''median of medians''' is an approximate [[median]] [[selection algorithm]], frequently used to supply a good pivot for an exact selection algorithm, most commonly [[quickselect]], that selects the ''k''th smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time. Using this approximate median as an improved pivot, the worst-case complexity of quickselect reduces from quadratic to ''linear'', which is also the asymptotically optimal worst-case complexity of any selection algorithm. In other words, the median of medians is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm (especially in the sense of worst-case complexity), by producing good pivot elements.

Median of medians can also be used as a pivot strategy in [[quicksort]], yielding an optimal algorithm, with worst-case complexity <math>O(n\log n)</math>.{{Citation needed|date=April 2024}} Although this approach optimizes the asymptotic worst-case complexity quite well, it is typically outperformed in practice by instead choosing random pivots for its average <math>O(n)</math> complexity for selection and average <math>O(n\log n)</math> complexity for sorting, without any overhead of computing the pivot.

Similarly, Median of medians is used in the hybrid [[introselect]] algorithm as a fallback for pivot selection at each iteration until kth smallest is found. This again ensures a worst-case linear performance, in addition to average-case linear performance: introselect starts with quickselect (with random pivot, default), to obtain good average performance, and then falls back to modified quickselect with pivot obtained from median of medians if the progress is too slow. Even though asymptotically similar, such a hybrid algorithm will have a lower complexity than a straightforward introselect up to a constant factor (both in average-case and worst-case), at any finite length.

The algorithm was published in {{harvtxt|Blum|Floyd|Pratt|Rivest|1973}}, and thus is sometimes called '''BFPRT''' after the last names of the authors. In the original paper the algorithm was referred to as '''PICK''',  referring to quickselect as '''FIND'''.

==Motivation==
Quickselect is linear-time on average, but it can require quadratic time with poor pivot choices. This is because quickselect is a [[divide and conquer algorithm|divide and conquer]] algorithm, with each step taking <math>O(n)</math> time in the size of the remaining search set. If the search set decreases exponentially quickly in size (by a fixed proportion), this yields a [[geometric series]] times the <math>O(n)</math> factor of a single step, and thus linear overall time. However, if the search set decreases slowly in size, such as linearly (by a fixed number of elements, in the worst case only reducing by one element each time), then a linear sum of linear steps yields quadratic overall time (formally, [[triangular number]]s grow quadratically). For example, the worst-case occurs when pivoting on the smallest element at each step, such as applying quickselect for the maximum element to already sorted data and taking the first element as pivot each time.

If one instead consistently chooses "good" pivots, this is avoided and one always gets linear performance even in the worst case. A "good" pivot is one for which we can establish that a constant proportion of elements fall both below and above it, as then the search set decreases at least by a constant proportion at each step, hence exponentially quickly, and the overall time remains linear. The median is a good pivot – the best for sorting, and the best overall choice for selection – decreasing the search set by half at each step. Thus if one can compute the median in linear time, this only adds linear time to each step, and thus the overall complexity of the algorithm remains linear.

The median-of-medians algorithm computes an approximate median, namely a point that is guaranteed to be between the 30th and 70th [[percentile]]s (in the middle 4 [[decile]]s). Thus the search set decreases by at least 30%. The problem is reduced to 70% of the original size, which is a fixed proportion smaller. Applying the same algorithm on the now smaller set recursively until only one or two elements remain results in a cost of <math>\frac{n}{1-0.7}\approx3.33 {n}</math>

==Algorithm==

As stated before, median-of-medians is used as a pivot selection strategy in the [[quickselect]] algorithm, which in [[pseudocode]] looks as follows. 
 
 '''function''' nthSmallest(list, n)
     index := select(list, 1, length of list, n) // Use select(list, 0, length of list - 1, n - 1) if list is [[zero-based numbering]]
     '''return''' list[index]

Be careful to handle <code>left</code>, <code>right</code> and <code>n</code> when implementing. The following pseudocode assumes that <code>left</code>, <code>right</code>, and the list use one-based numbering and that <code>select</code> is initially called with 1 as the argument to <code>left</code> and the length of the list as the argument to <code>right</code>. Note that this returns the index of the n'th smallest number after rearranging the list, rather than the actual value of the n'th smallest number.

 '''function''' select(list, left, right, n)
     '''loop'''
         '''if''' left = right '''then'''
             '''return''' left
         pivotIndex := pivot(list, left, right)
         pivotIndex := partition(list, left, right, pivotIndex, n)
         '''if''' n = pivotIndex '''then'''
             '''return''' n
         '''else if''' n < pivotIndex '''then'''
             right := pivotIndex - 1
         '''else'''
             left := pivotIndex + 1

Subroutine {{mono|pivot}} is the actual median-of-medians algorithm. It divides its input (a list of length {{mvar|n}}) into groups of at most five elements, computes the median of each of those groups using some subroutine, then [[Recursion (computer science)|recursively]] computes the true median of the <math>\frac{n}{5}</math> medians found in the previous step:.<ref name="clrs">{{Introduction to Algorithms|3|pages=220}}</ref> Note that {{mono|pivot}} calls {{mono|select}}; this is an instance of [[mutual recursion]].

 '''function''' pivot(list, left, right)
     ''// for 5 or less elements just get median''
     '''if''' right − left < 5 '''then'''
         '''return''' partition5(list, left, right)
     ''// otherwise move the medians of five-element subgroups to the first n/5 positions''
     '''for''' i '''from''' left '''to''' right '''in steps of''' 5
         ''// get the median position of the i'th five-element subgroup''
         subRight := i + 4
         '''if''' subRight > right '''then'''
             subRight := right
         median5 := partition5(list, i, subRight)
         swap list[median5] and list[left + floor((i − left) / 5)]
 
     ''// compute the median of the n/5 medians-of-five''
     mid := floor((right − left) / 10) + left + 1
     '''return''' select(list, left, left + floor((right − left) / 5), mid)

===Partition helper functions===
{{See also|Dutch national flag problem}}

There is a subroutine called {{mono|partition}} that can, in linear time, group a list (ranging from indices <code>left</code> to <code>right</code>) into three parts, those less than a certain element, those equal to it, and those greater than the element ([[Dutch national flag problem|a three-way partition]]). The grouping into three parts ensures that the median-of-medians maintains linear execution time in a case of many or all coincident elements. Here is pseudocode that performs a partition about the element <code>list[pivotIndex]</code>:

 '''function''' partition(list, left, right, pivotIndex, n)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  ''// Move pivot to end''
     storeIndex := left
     ''// Move all elements smaller than the pivot to the left of the pivot''
     '''for''' i '''from''' left '''to''' right − 1 '''do'''
         '''if''' list[i] < pivotValue '''then'''
             swap list[storeIndex] and list[i]
             increment storeIndex
     ''// Move all elements equal to the pivot right after''
     ''// the smaller elements''
     storeIndexEq := storeIndex
     '''for''' i '''from''' storeIndex '''to''' right − 1 '''do'''
         '''if''' list[i] = pivotValue '''then'''
             swap list[storeIndexEq] and list[i]
             increment storeIndexEq
     swap list[right] and list[storeIndexEq]  ''// Move pivot to its final place''
     ''// Return location of pivot considering the desired location n''
     '''if''' n < storeIndex '''then'''
         '''return''' storeIndex  ''// n is in the group of smaller elements''
     '''if''' n ≤ storeIndexEq '''then'''
         '''return''' n  ''// n is in the group equal to pivot''
     '''return''' storeIndexEq ''// n is in the group of larger elements''

The {{mono|partition5}} subroutine selects the median of a group of at most five elements; an easy way to implement this is [[insertion sort]], as shown below.{{r|clrs}} It can also be implemented as a [[decision tree]].

 '''function''' partition5(list, left, right)
     i := left + 1
     '''while''' i ≤ right '''do'''
         j := i
         '''while''' j > left and list[j−1] > list[j] '''do'''
             swap list[j−1] and list[j]
             j := j − 1
         i :=  i + 1
 
     '''return''' left + (right - left) / 2

== Properties of pivot ==
Of the <math>\frac{n}{5}</math> groups, half the number of groups <math>\left(\frac{1}{2}\times\frac{n}{5}=\frac{n}{10}\right)</math> have their median less than the pivot (Median of Medians). Also, another half the number of groups <math>\left(\text{again, }\frac{1}{2}\times\frac{n}{5}=\frac{n}{10}\right)</math> have their median greater than the pivot. In each of the <math>\frac{n}{10}</math> groups with median less than the pivot, there are two elements that are smaller than their respective medians, which are smaller than the pivot. Thus, each of the <math>\frac{n}{10}</math> groups have at least 3 elements that are smaller than the pivot. Similarly, in each of the <math>\frac{n}{10}</math> groups with median greater than the pivot, there are two elements that are greater than their respective medians, which are greater than the pivot. Thus, each of the <math>\frac{n}{10}</math> groups have at least 3 elements that are greater than the pivot. Hence, the pivot is less than <math>3\times\frac{n}{10}</math> elements and greater than another <math>3\times\frac{n}{10}</math> elements. Thus the chosen median splits the ordered elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm. To visualize:

{|class="wikitable" border=1
|+ One iteration on a randomized set of 100 elements from 0 to 99
!
| bgcolor=gray|12||||bgcolor=gray|15||||bgcolor=gray|11||||bgcolor=gray|2||||bgcolor=gray|9||||bgcolor=gray|5||||bgcolor=gray|0||||bgcolor=gray|7||||bgcolor=gray|3||||bgcolor=gray|21||||bgcolor=gray|44||||bgcolor=gray|40||||bgcolor=gray|1||||bgcolor=gray|18||||bgcolor=gray|20||||bgcolor=gray|32||||bgcolor=gray|19||||bgcolor=gray|35||||bgcolor=gray|37||||bgcolor=gray|39
|-
!
| bgcolor=gray|13||||bgcolor=gray|16||||bgcolor=gray|14||||bgcolor=gray|8||||bgcolor=gray|10||||bgcolor=gray|26||||bgcolor=gray|6||||bgcolor=gray|33||||bgcolor=gray|4||||bgcolor=gray|27||||bgcolor=white|49||||bgcolor=gray|46||||bgcolor=white|52||||bgcolor=gray|25||||bgcolor=white|51||||bgcolor=gray|34||||bgcolor=gray|43||||bgcolor=white|56||||bgcolor=white|72||||bgcolor=white|79
|-
! Medians
| bgcolor=gray|17||||bgcolor=gray|23||||bgcolor=gray|24||||bgcolor=gray|28||||bgcolor=gray|29||||bgcolor=gray|30||||bgcolor=gray|31||||bgcolor=gray|36||||bgcolor=gray|42||||bgcolor=red|47||||bgcolor=white|50||||bgcolor=white|55||||bgcolor=white|58||||bgcolor=white|60||||bgcolor=white|63||||bgcolor=white|65||||bgcolor=white|66||||bgcolor=white|67||||bgcolor=white|81||||bgcolor=white|83
|-
!
| bgcolor=gray|22||||bgcolor=gray|45||||bgcolor=gray|38||||bgcolor=white|53||||bgcolor=white|61||||bgcolor=gray|41||||bgcolor=white|62||||bgcolor=white|82||||bgcolor=white|54||||bgcolor=white|48||||bgcolor=white|59||||bgcolor=white|57||||bgcolor=white|71||||bgcolor=white|78||||bgcolor=white|64||||bgcolor=white|80||||bgcolor=white|70||||bgcolor=white|76||||bgcolor=white|85||||bgcolor=white|87
|-
!
| bgcolor=white|96||||bgcolor=white|95||||bgcolor=white|94||||bgcolor=white|86||||bgcolor=white|89||||bgcolor=white|69||||bgcolor=white|68||||bgcolor=white|97||||bgcolor=white|73||||bgcolor=white|92||||bgcolor=white|74||||bgcolor=white|88||||bgcolor=white|99||||bgcolor=white|84||||bgcolor=white|75||||bgcolor=white|90||||bgcolor=white|77||||bgcolor=white|93||||bgcolor=white|98||||bgcolor=white|91
|-
|}

(red = "(one of the two possible) median of medians", gray = "number < red", white = "number > red")

5-tuples are shown here sorted by median, for clarity.  Sorting the tuples is not necessary because we only need the median for use as pivot element.

Note that all elements above/left of the red (30% of the 100 elements) are less, and all elements below/right of the red (another 30% of the 100 elements) are greater.

== Proof of linear running time ==

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians has size <math>\frac{n}{5}</math>, while the other recursive call recurses on at most 70% of the list. Let <math>T(n)</math> be the time it takes to run a median-of-medians Quickselect algorithm on an array of size <math>n</math>. Then we know this time is:
:<math>T(n) \leq T(n/5) + T(n \cdot 7/10) + c \cdot n,</math>

where
* the <math>T\left(\frac{n}{5}\right)</math> part is for finding the ''true'' median of the <math>\frac{n}{5}</math> medians, by running an (independent) Quickselect on them (since finding the median is just a special case of selecting a ''k''-smallest element)
* the <math>O(n)</math> term <math>c\cdot n</math> is for the partitioning work to create the two sides, one of which our Quickselect will recurse (we visited each element a constant number of times in order to form them into n/5 groups and take each median in <math>O(1)</math> time).
* the <math>T\left(\frac{7n}{10}\right)</math> part is for the actual Quickselect recursion (for the worst case, in which the ''k''-th element is in the bigger partition that can be of size <math>\frac{7n}{10}</math> maximally)

By induction:
:<math>T(n) \leq 10 \cdot c \cdot n \in O(n).</math>

== Analysis ==
The key step is reducing the problem to selecting in two lists whose total length is shorter than the original list, plus a linear factor for the reduction step. This allows a simple induction to show that the overall running time is linear.

The specific choice of groups of five elements is explained as follows. Firstly, computing median of an odd list is faster and simpler; while one could use an even list, this requires taking the average of the two middle elements, which is slower than simply selecting the single exact middle element. Secondly, five is the smallest odd number such that median of medians works. With groups of only three elements, the resulting list of medians to search in is length <math>\frac{n}{3}</math>, and reduces the list to recurse into length <math>\frac{2}{3}n</math>, since it is greater than 1/2 × 2/3 = 1/3 of the elements and less than 1/2 × 2/3 = 1/3 of the elements. Thus this still leaves <math>n</math> elements to search in, not reducing the problem sufficiently. The individual lists are shorter, however, and one can bound the resulting complexity to <math>O(n \log n)</math> by the [[Akra–Bazzi method]], but it does not prove linearity.

Conversely, one may instead group by <math>g</math> = seven, nine, or more elements, and this does work. This reduces the size of the list of medians to <math>\frac{n}{g}</math>'','' and the size of the list to recurse into asymptotes at 3''n''/4 (75%), as the quadrants in the above table approximate 25%, as the size of the overlapping lines decreases proportionally. This reduces the scaling factor from 10 asymptotically to 4, but accordingly raises the <math>c</math> term for the partitioning work. Finding the median of a larger group takes longer, but is a constant factor (depending only on <math>g</math>), and thus does not change the overall performance as ''n'' grows. In fact, considering the number of comparisons in the worst case, the constant factor is <math>\frac{2g(g-1)}{g-3}</math>.

If one instead groups the other way, say dividing the <math>n</math> element list into 5 lists, computing the median of each, and then computing the median of these – i.e., grouping by a constant fraction, not a constant number – one does not as clearly reduce the problem, since it requires computing 5 medians, each in a list of <math>\frac{n}{5}</math> elements, and then recursing on a list of length at most <math>\frac{7}{10}n</math>. As with grouping by 3, the individual lists are shorter, but the overall length is no shorter – in fact longer – and thus one can only prove superlinear bounds. Grouping into a square of <math>\sqrt{n}</math> lists of length <math>\sqrt{n}</math> is similarly complicated.

== References ==
{{reflist}}
{{refbegin}}
* {{Cite journal | last1 = Blum | first1 = M. | authorlink1 = Manuel Blum| last2 = Floyd | first2 = R. W. | authorlink2 = Robert W. Floyd| last3 = Pratt | first3 = V. R. | authorlink3 = Vaughan Pratt| last4 = Rivest | first4 = R. L. | authorlink4 = Ron Rivest| last5 = Tarjan | first5 = R. E. | authorlink5 = Robert Tarjan | title = Time bounds for selection | doi = 10.1016/S0022-0000(73)80033-9 | journal = Journal of Computer and System Sciences | volume = 7 | issue = 4  | pages = 448–461 | date =August 1973 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf| doi-access = free }}
{{refend}}

== External links ==
* "[http://www.ics.uci.edu/~eppstein/161/960130.html Lecture notes for January 30, 1996: Deterministic selection]", ''ICS 161: Design and Analysis of Algorithms,'' David Eppstein

[[Category:Selection algorithms]]