medianofmedians

Median of medians is a deterministic selection algorithm used to find the k-th smallest element in an unsorted list with guaranteed worst-case linear time. It is the pivot selection strategy employed by the BFPRT algorithm, named after Blum, Floyd, Pratt, Rivest, and Tarjan, who introduced it in 1973.

How it works: the input is divided into groups of five elements. Each group is sorted (or its median is determined) and the median of each group is collected. The medians form a new list, and the median of this list is computed recursively; this value serves as a pivot. The original array is partitioned around the pivot into elements smaller and larger than the pivot. If the k-th element lies in the left partition, the algorithm recurses on that side; otherwise it recurses on the right side, adjusting k accordingly. This process guarantees progress by removing a fixed fraction of elements in each step.

Complexity and properties: the median-of-medians pivot ensures that a substantial fraction of elements is discarded in each partition, which yields a worst-case time complexity of O(n). The algorithm is in-place and uses only a small amount of additional space, with the main cost being recursive calls and partitioning. While asymptotically optimal, the method is more complex to implement than randomized Quickselect and is less common in practical use, though it provides strong worst-case guarantees.

Variants and history: using groups of five is standard and balances simplicity with the linear-time bound; other group sizes exist but offer different trade-offs. The method is a cornerstone of deterministic selection and order-statistics theory.