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.
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.
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 }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 }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 }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 }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.