A CHARACTERIZATION OF THE SET OF FIXED POINTS OF THE QUICKSORT TRANSFORMATION

The limiting distribution µ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T —unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of T if and only if it is the convolution of µ with a Cauchy distribution of arbitrary center and scale. In particular, therefore, µ is the unique fixed point of T having zero mean