This note shows a new implicit data structure, called a set of nested s-heaps, for deleting the maximum value of n elements in 2 long n comparisons. Nested s-heaps can be used to improve the efficiency of Smoothsort.

Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).