ASYMPTOTIC-DISTRIBUTION THEORY FOR HOARES SELECTION ALGORITHM

We investigate the asymptotic behaviour of the distribution of the num ber of comparisons needed by a quicksort-style selection algorithm tha t finds the lth smallest in a set of n numbers. Letting n tend to infi nity and considering the values l = 1, ..., n simultaneously we obtain a limiting stochastic process. This process admits various interpreta tions: it arises in connection with a representation of real numbers i nduced by nested random partitions and also in connection with expecte d path lengths of a random walk in a random environment on a binary tr ee.