Abstract
The selection problem—finding the $i$-th order statistic of $n$ elements—has long been dominated by the deterministic "Median of Medians" algorithm (BFPRT). A persistent belief in computer science is that this algorithm requires group sizes of at least 5 to maintain linear $O(n)$ worst-case complexity. This paper challenges that notion, demonstrating that group sizes of 2, 3, and 4 can achieve linear time through novel algorithmic variants such as the repeated step, shifting target, and hyperpair algorithms.
The "Magic Number 5" Myth
Since the introduction of the BFPRT algorithm in 1973, textbooks have taught that using group sizes smaller than 5 leads to superlinear complexity, specifically $\Omega(n \log n)$. This conclusion stems from the standard recurrence $T(n) \le T(n/g) + T(n(1 - \frac{g+1}{2g})) + O(n)$, where $g$ is the group size. For $g=3$, the recurrence becomes $T(n) \le T(n/3) + T(2n/3) + O(n)$, which indeed solves to $O(n \log n)$.
However, the authors point out that this logic assumes the two recursive calls are independent and that the algorithm's structure is fixed. By modifying the algorithm's steps, the "quality" of the pivot can be improved or the cost of finding it reduced, allowing for linear time even with small groups.
Novel Small-Group Algorithms
The paper introduces three primary strategies to achieve linearity with small groups:
1. The Repeated Step Algorithm
For group sizes 3 or 4, the algorithm performs the "median of medians" step twice. By finding the median of a set of medians, the algorithm effectively identifies a "ninther" (median of 9) or similar higher-order statistic. This extra work in the pivot selection phase ensures that the subsequent partition step discards a large enough fraction of the array to keep the total work linear.
2. The Shifting Target Algorithm
Specifically designed for group size 4, where there is no unique median, this algorithm alternates between using the lower and upper medians of each group. By strategically "shifting" the target pivot over successive recursive calls, the algorithm balances the partition sizes over time.
3. The Hyperpair Algorithm
The most radical departure is the hyperpair algorithm for group size 2. It uses a hierarchical pairing structure to identify a pivot. By repeating the pairing process multiple times, it builds a tree-like structure (a hyperpair) that guarantees a significant portion of the elements are either smaller or larger than the chosen pivot.
Empirical Performance
Theoretical linearity is matched by practical efficiency. In experiments with 10 million random integers, the small-group variants often outperformed the classic Group-5 BFPRT.
- Hybrid (Group 4): Achieved the best performance with approximately $18n$ comparisons.
- Repeated Step (Group 3): Required ~21n comparisons.
- Classic BFPRT (Group 5): Required ~22n comparisons.
The lower overhead of finding medians in smaller groups (3 comparisons for size 3 vs. 6 for size 5) translates to faster real-world execution times, with the Group-4 Hybrid being nearly 22% faster than the standard Group-5 approach.
Conclusion
This work successfully debunks the "Magic Number 5" myth. By showing that $O(n)$ selection is possible for any group size $g \ge 2$, the authors open new avenues for optimizing selection in practice. While the original 1973 algorithm's complexity for $g=3$ remains an open theoretical question, these new variants provide efficient, linear-time alternatives that challenge decades of textbook convention.
Summary updated