Analysis of Hoare's FIND Algorithm with Median-of-three
Partition

Abstract.
Hoare's \textsc{Find} algorithm can be used to select the $j$th element out of
a file of $n$ elements. It bears a remarkable similarity to Quicksort;
in each pass of the algorithm, a pivot element is used to split the
file into two subfiles, and recursively the algorithm proceeds with
the subfile that
contains the sought element. As in Quicksort, different strategies for
selecting the pivot are reasonable. In this paper, we consider the
Median--of--three version, where the pivot element is chosen as the
median of a random sample of three elements. Establishing some
hypergeometric differential equations, we find explicit
formul{\ae} for both the average number of passes and comparisons.
We compare these results with the corresponding ones for the basic
partition strategy.