A Gaussian limit process for optimal FIND algorithms

We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to $c\cdot n^{\alpha }$ are chosen, where $0<\alpha \le \frac{1}{2}$, $c>0$ and $n$ is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as $n\to \mathrm{\infty }$, which depends on $\alpha$. The proof relies on a contraction argument for probability distributions on c{`a}dl{`a}g functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.