Median of Medians Simulation

Controls

Current Frame

Step Detail

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

Guarantee Mechanism

Grouping by 5 ensures the pivot is never among the worst 30% nor best 30% of remaining elements: at least 3/10 are <= pivot and 3/10 are >= pivot, shrinking the problem linearly. This yields recurrence T(n) = T(n/5) + T(7n/10) + O(n) ⇒ linear time.