Fill, James Allen; Janson, Svante A characterization of the set of fixed points of the quicksort transformation. (English) Zbl 0943.68192 Electron. Commun. Probab. 5, 77-84 (2000). 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. Cited in 1 ReviewCited in 15 Documents MSC: 68W40 Analysis of algorithms 68P10 Searching and sorting 60E05 Probability distributions: general theory 60E10 Characteristic functions; other transforms Keywords:characteristic function; smoothing transformation; domain of attraction; coupling; integral equation × Cite Format Result Cite Review PDF Full Text: DOI EuDML EMIS