Median of Medians Theory

Pivot Quality Argument

Group the n elements into ⌈n/5⌉ blocks of 5. Sorting each small block yields its median. Selecting the median of these medians gives a pivot p with the guarantee that at least 3n/10 elements are >= p and at least 3n/10 are <= p.

Half of the block medians ≥ p. Each such median dominates (is ≥) at least two elements in its block, giving ≥ (n/10)*3 = 3n/10 elements ≥ p (handling uneven last group). Symmetry for ≤ p.

Recurrence

T(n) = T(n/5) + T(7n/10) + O(n)

First term chooses pivot (select median among block medians). Second term recurses into the larger side (≤ 7n/10 elements). Linear term groups, sorts tiny blocks, partitions.

Solves to O(n); constants higher than randomized quickselect.

Pseudocode

1function select(arr, k):
2  if small(arr): return sort(arr)[k]
3  partition arr into groups of 5
4  medians = [median(g) for g in groups]
5  pivot = select(medians, len(medians)//2)
6  L, E, G = partition(arr, pivot)
7  recurse into appropriate partition