Asymptotic distribution theory for Haore’s selection algorithm

The authors investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds te lth smallest in a set of n numbers. Letting n tend to infinity and considering the values l=1,...,n simulatneously they obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.