Deterministic median-of-medians selection: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Sort groups of five, recursively select their median as pivot, and keep only the partition containing the requested rank.

Sort small groups of five, move their medians into a prefix, and recursively select the median of that prefix. Partition the original range around this deterministic pivot and continue only in the part containing the target rank.

Open the 3D visualization

Deterministic median-of-medians selection example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Deterministic median-of-medians selection

Teaching worst-case linear selection without random pivot assumptions.

Choosing an alternative

Quickselect has fast average behavior but can be quadratic with poor pivots. The median-of-medians pivot guarantees sufficient progress; its larger constants often make it less attractive for ordinary small inputs.

Worked example: input and state changes

Example input

9,1,8,2,7,3,6,4,5,0,10,11 | 5

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Select zero-based rank 5 using deterministic groups of five.

    State at this checkpoint
    {
      "values": [
        9,
        1,
        8,
        2,
        7,
        3,
        6,
        4,
        5,
        0,
        10,
        11
      ],
      "active": [],
      "result": -1
    }
  2. Step 5: Sort a group of at most five.

    State at this checkpoint
    {
      "values": [
        7,
        4,
        1,
        8,
        9,
        0,
        3,
        2,
        5,
        6,
        10,
        11
      ],
      "active": [
        10,
        11
      ],
      "result": -1
    }
  3. Step 10: Keep the lower partition.

    State at this checkpoint
    {
      "values": [
        4,
        1,
        6,
        5,
        0,
        3,
        2,
        7,
        9,
        10,
        8,
        11
      ],
      "active": [],
      "result": -1
    }
  4. Step 15: Select the median of 2 group medians.

    State at this checkpoint
    {
      "values": [
        4,
        3,
        0,
        5,
        6,
        2,
        1,
        7,
        9,
        10,
        8,
        11
      ],
      "active": [],
      "result": -1
    }
  5. Step 20: Rank 5 contains 5. The surrounding partitions satisfy <= and >=.

    State at this checkpoint
    {
      "values": [
        3,
        0,
        1,
        2,
        4,
        5,
        6,
        7,
        9,
        10,
        8,
        11
      ],
      "active": [
        5
      ],
      "result": 5
    }

Expected final state

Rank 5 contains 5. The surrounding partitions satisfy <= and >=.

Complexity and input bounds

Family: Searching. Time complexity: O(n) worst-case time.

Implementation detail: Inputs have at most 64 values and use zero-based ranks. Groups of at most five are insertion-sorted; an even partial group takes its upper middle. Downloads return the selected value and rearrange the input into a partial partition while preserving its multiset. Tests independently check sorted ranks and the exact recursive partition result.

Space complexity: O(log n) active recursive or explicit-stack state with fixed portable buffers, plus saved visualization frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..64 values 0..99 | zero-based rank 0..n-1. The array is partitioned, not fully sorted.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Select the median of the medians recursively rather than merely taking the median of an unsorted prefix. Preserve the original target index while narrowing partitions. Handle duplicate values with an equal partition and include partial final groups.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// Deterministic BFPRT selection, n 1..64 values 0..99, zero-based k 0..n-1. Returns selected value, mutating a into a partial partition: a[k] is selected, earlier values <= it, later values >= it. Multiset is preserved; array need not be fully sorted and the method is not stable. Groups of five use insertion sort; partial even groups take their upper middle; the pivot is selected recursively from group medians, then three-way partitioned. Invalid n/rank returns -1 without mutation. O(n) worst-case time, O(log n) active recursion/explicit-stack state with fixed portable buffers. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, k) {
    if (n < 1 || n > 64 || k < 0 || k >= n) { return -1; }
    let lows = Array(256).fill(0); let highs = Array(256).fill(0); let ranks = Array(256).fill(0); let stages = Array(256).fill(0); let depth = 0; let low = 0; let high = 0; let target = 0; let begin = 0; let end = 0; let key = 0; let cursor = 0; let count = 0; let median = 0; let temp = 0; let selected = 0; let pivot = 0; let lt = 0; let gt = 0;
    highs[0] = n-1; ranks[0] = k;
    while (depth >= 0) { low = lows[depth]; high = highs[depth]; target = ranks[depth];
     if (stages[depth] == 0) { if (high-low+1 <= 5) { begin = low; end = high; for (let position = begin+1; position <= end; position++) { key = a[position]; cursor = position-1; while (cursor >= begin && a[cursor] > key) { a[cursor+1] = a[cursor]; cursor--; } a[cursor+1] = key; } selected = a[target]; depth--; }
     else { count = 0; for (let start = low; start <= high; start += 5) { begin = start; end = start+4; if (end > high) { end = high; } for (let position = begin+1; position <= end; position++) { key = a[position]; cursor = position-1; while (cursor >= begin && a[cursor] > key) { a[cursor+1] = a[cursor]; cursor--; } a[cursor+1] = key; } median = start+((end-start+1) >> 1); temp = a[low+count]; a[low+count] = a[median]; a[median] = temp; count++; }
     stages[depth] = 1; depth++; lows[depth] = low; highs[depth] = low+count-1; ranks[depth] = low+(count >> 1); stages[depth] = 0;
     } }
     else { pivot = selected; lt = low; cursor = low; gt = high;
     while (cursor <= gt) { if (a[cursor] < pivot) { temp = a[lt]; a[lt] = a[cursor]; a[cursor] = temp; lt++; cursor++; } else { if (a[cursor] > pivot) { temp = a[cursor]; a[cursor] = a[gt]; a[gt] = temp; gt--; } else { cursor++; } } }
     if (target < lt) { highs[depth] = lt-1; stages[depth] = 0; } else { if (target > gt) { lows[depth] = gt+1; stages[depth] = 0; } else { selected = pivot; depth--; } }
     }
    }
    return selected;
}

Source

Foundational worst-case linear selection research. The playground uses the standard groups-of-five median-of-medians formulation; it does not claim the paper optimized PICK comparison constant.

  • Time Bounds for Selection
    Manuel Blum; Robert W. Floyd; Vaughan Pratt; Ronald L. Rivest; Robert E. Tarjan (1973). Foundational deterministic selection research.