Median of Medians

Deterministic selection producing a worst-case linear pivot quality by recursively selecting the median of group medians.

Goal

k-th smallest

Selection target

Worst-Case

O(n)

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

Discard

>=30%

Each iteration min shrink

Key Stages

Group elements into blocks of 5.
Sort each group and extract its median.
Select the median of these medians (pivot).
Partition original array by pivot.
Recurse only into side containing index k.

Guarantee Logic

At least half of group medians are >= pivot and each such median is >= two elements in its group. Similarly for <= pivot. This yields >= 3n/10 elements eliminated every partition.

Symmetry and floor/ceiling rounding preserve a linear discard factor.

Why 5?

Smaller groups reduce discard percentage.
Larger groups increase sorting overhead.
Size 5 balances pivot quality and constant factors.

View Theory Run Simulation

Karatsuba Multiplication