×

A characterization of the set of fixed points of the quicksort transformation. (English) Zbl 0943.68192

Summary: The limiting distribution \(m\) 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 \(\mu\) with a Cauchy distribution of arbitrary center and scale. In particular, therefore, \(\mu\) is the unique fixed point of \(T\) having zero mean.

MSC:

68W40 Analysis of algorithms
68P10 Searching and sorting
60E05 Probability distributions: general theory
60E10 Characteristic functions; other transforms