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 i th 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.