Chapter notes

The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest, and Tarjan [43]. The fast average-time version is due to Hoare [146]. Floyd and Rivest [92] have developed an improved average-time version that partitions around an element recursively selected from a small sample of the elements.

It is still unknown exactly how many comparisons are needed to determine the median. A lower bound of 2n comparisons for median finding was given by Bent and John [38]. An upper bound of 3n was given by Schonhage, Paterson, and Pippenger [265]. Dor and Zwick [79] have improved on both of these bounds; their upper bound is slightly less than 2.95n and the lower bound is slightly more than 2n. Paterson [239] describes these results along with other related work.