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 kth 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 O ( n log n ) {\displaystyle O(n\log n)} . The median of medians algorithm guarantees a worst-case runtime of O(n) by recursively selecting good pivot elements, discarding at least 30% of elements at each step. 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 O ( n ) {\displaystyle O(n)} complexity for selection and average O ( n log n ) {\displaystyle O(n\log n)} 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 1973 and is sometimes called BFPRT after the last names of the authors (Blum, Floyd, Pratt, Rivest, Tarjan). 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, with each step taking O ( n ) {\displaystyle O(n)} 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 O ( n ) {\displaystyle O(n)} 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 numbers 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 percentiles (in the middle 4 deciles). 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 n 1 − 0.7 ≈ 3.33 n {\displaystyle {\frac {n}{1-0.7}}\approx 3.33{n}}
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 median(list) if length(list) is odd then value := nthSmallest(list, length(list) / 2) else value := 0.5 * (nthSmallest(list, length(list) / 2 - 1) + nthSmallest(list, length(list) / 2)) return value
function nthSmallest(list, n) index := select(list, 1, length(list), n) return list[index]
Be careful to handle left, right and n when implementing. The following pseudocode assumes that left, right, and the list use one-based numbering and that select is initially called with 1 as the argument to left and the length of the list as the argument to right. 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
… excerpt ends here. Continue reading the full article.
