Expected Time Bounds for Selection A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the ith smallest of n numbers is n+min(i,n-i)+o(n). A lower bound within 9 percent of the above formula is also derived. CACM March, 1975 Floyd, R. W. Rivest, R. L. selection, computational complexity, medians, tournaments, quantiles 5.30 5.39 CA750304 JB January 9, 1978 4:52 PM 1919 4 2784 2191 4 2784 2388 4 2784 2783 4 2784 2784 4 2784 2784 4 2784 2784 4 2784 3054 4 2784 3121 4 2784 864 4 2784 1729 5 2784 309 5 2784 2783 5 2784 2784 5 2784 2784 5 2784 2784 5 2784 2837 5 2784 2784 6 2784 2842 6 2784