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 \frac{n}{5} medians found in the previous step:. Note that calls ; this is an instance of
mutual recursion.
function pivot(list, left, right)
// for 5 or less elements just get median if right − left 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 There is a subroutine called that can, in linear time, group a list (ranging from indices left to right) into three parts, those less than a certain element, those equal to it, and those greater than the element (
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 list[pivotIndex]:
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] 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 ==