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

In Hoare's (1961) original version of the algorithm FIND the partitioning e lement 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.