Median of Medians

A deterministic selection algorithm that finds the k-th smallest element in linear time O(n) by guaranteeing a balanced pivot.

Step 1 / 0

Current Active Subset (n=0)

Dataset Options

Array Size25

Find k-th smallest (k)12

State Metrics

Recursion Depth0

Target Index (k)12

Pseudocode

1function select(A, k):
2  if length(A) <= 5: return sort(A)[k]
3  groups = divide A into groups of 5
4  medians = [median(g) for g in groups]
5  pivot = select(medians, length(medians)/2)
6  L, E, G = partition A around pivot
7  if k < length(L): return select(L, k)
8  if k < length(L) + length(E): return pivot
9  return select(G, k - length(L) - length(E))

Linear Guarantee

By choosing the median of group (size 5) medians, we guarantee that the pivot is at least greater than 30% and less than 30% of the elements. This prevents the "unlucky" pivots that cause O(n^2) in basic Quickselect.