wild-inter.net Selection by rank

Median of Medians

Deterministic selection by rank, in place. The pivot is not guessed: the input is cut into groups of five, each group is sorted, the five medians are gathered at the front of the range, and the algorithm calls itself to select the median of those — that pivot is then good enough to throw away a constant fraction every round. Everything happens inside the one array; the frame shows the range still in play.

The array
Comparisons so far
Call stack

      
Both procedures  ·  the pseudocode this page executes
choosePivotMoM
quickselectMoM

Two black boxes

sort and partition are not unfolded here — only their effect on the array is animated. Their cost is charged as stated: sort of a block counts the comparisons an insertion sort makes on it, partition counts r − l.

Note what partition works on: the whole range, including the up to four leftover elements at the end that were never part of any group of five. Only the medians of complete groups take part in choosing the pivot.

Load an input  ·  plain-text format
Numbers separated by spaces, commas or newlines — duplicates allowed. An optional line k <rank> sets the rank being searched for (0-based, as on the slides).

Everything is in place: what you see is the one array being permuted, never a copy.