  We show that several versions of Floyd and Rivest's improved algorithm Select
for finding the $k$th smallest of $n$ elements require at most
$n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high
probability. This rectifies the analysis of Floyd and Rivest, and extends it to
the case of nondistinct elements. Encouraging computational results on large
median-finding problems are reported.
