Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
Finding the exact minimum comparisons needed to sort small lists
Researchers determined that finding the 7th smallest element among 16 items requires exactly 28 comparisons in the worst case—better than the previous best-known result of 30. Using computer search and formal verification, they also improved bounds for related problems with 16 and 17 elements, pinpointing the precise efficiency limits of comparison-based selection algorithms.
Comparison counts determine how fast sorting and selection algorithms run on real data. These exact bounds provide a performance ceiling that algorithm designers and hardware engineers use as a benchmark; knowing the absolute minimum proves whether current methods are truly optimal or leave room for improvement. The formal verification methods developed here provide a template for settling other open questions in algorithm theory.