On the median-of-k version of Hoare's selection algorithm

Institut für Mathematische Stochastik, Universität Hannover, Postfach 60 09, 30060 Hannover, Germany; rgrubel@stochastik.uni-hannover.de.

Received: May 1998
Accepted: March 1999

Abstract

In Hoare's (1961) original version of the algorithm   the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.