Density and Generating Functions of a Limiting Distribution for Quicksort

Kok Hooi Tan and Petros Hadjicostas

Abstract:

Let be the random number of comparisons needed to sort a list of length by Quicksort. Régnier (1989), Rösler (1991), and Hennequin (1991) showed that converges in distribution to some random variable . In addition, Hennequin derived a formula for the cumulants of . Using results of the above authors we derive properties of the generating functions of . Analytical formulas for these functions are derived, but the formulas are not in closed form. Using the method of successive substitution (Eddy and Schervish, 1992), we obtain numerical estimates for some of the generating functions. Some theoretical aspects of the last method are investigated. In addition, we prove that is absolutely continuous with respect to the Lebesgue measure, and that its distribution is supported on the entire real line.

Keywords: Gamma function, generating functions, limiting distribution, Quicksort, Stirling numbers, successive substitution, zeta function.