Selection Algorithms with Small Groups

Ke Chen, Adrian DumitrescuarXiv 2014 · DOI · arXiv

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.

Pivot quality for group size 4

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.

Hyperpair construction for group size 2

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

Abstract

We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $Ω(n \log{n})$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.
BibTeX
@misc{chen2014selection,
  author = {Ke Chen and Adrian Dumitrescu},
  title = {{Selection Algorithms with Small Groups}},
  year = {2014},
  eprint = {1409.3600},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.3600},
}
Figure