Floyd-Rivest algorithm

The Floyd-Rivest algorithm is a selection algorithm developed by Robert W. Floyd and Ronald L. Rivest that has an optimal expected number of comparisons within lower-order terms. It is functionally equivalent to quickselect but runs faster in practice on average, with an expected running time of linear order. It is a divide-and-conquer method: it draws a small random sample from the list, recursively selects two pivot elements from that sample so that the wanted element is expected to lie between them, partitions the rest of the list around the two pivots, and then recurses into the one part that must contain the kth smallest element. With a sample size of order n to the two thirds power times a log factor it reaches n plus min(k, n minus k) expected comparisons plus a lower-order term, and refining the pivots as it goes tightens that further. It was first presented in a 1973 Stanford University technical report, where it was called SELECT and paired with PICK, the median of medians method, and was then published in Communications of the ACM.