Median of Medians

Given n elements from a totally ordered universe, find kth smallest.

• Divide and conquer, $O(n)$
• General problem
  • Minimum: $k = 1$
  • Maximum: $k = n$
  • Median: $k = \lfloor \frac{n + 1}{2} \rfloor$.
• Possible approaches
  • $O(n)$ compares for min or max
  • $O(n \log n)$ compares by sorting
  • $O(n \log k)$ compares with a binary heap. (max heap with k smallest)

Applications: Order statistics; find the “top k”; bottleneck paths, …

Q. Can we do it with $O(n)$ compares?
A. Yes! Selection is easier than sorting.

Choosing the pivot element #

• Divide n elements into $\lfloor \frac{n}{5} \rfloor$ groups of 5 elements each (plus extra).
• Find median of each group (except extra).
• Find median of $\lfloor \frac{n}{5} \rfloor$ medians recursively.
• Use median-of-medians as pivot element.

MOM-SELECT(A, k):
  n = |A|
  if (n < 50)
    return kth smallest of element of A via mergesort

  Group A into ⎣n / 5⎦ groups of 5 elements each (ignore leftovers)
  B = median of each group of 5
  p = MOM-SELECT(B, ⎣n / 10⎦) # median of medians

  (L, M, R) = PARTITION-3-WAY(A, p)
  if (k ≤ |L|)
    return MOM-SELECT(L, k)
  else if (k > |L| + |M|)
    return MOM-SELECT(R, k - |L| - |M|)
  else
    return p