Quicksort asymptotics

The number of comparisons X, used by Quicksort to sort an array of it distinct numbers has mean mu(n) of order n log n and standard deviation of order it. Using different methods, Regnier and Rosler each showed that the normalized variate Y-n := (X-n - mu(n))/n converges in distribution, say to Y; the distribution of Y can be characterized as the unique fixed point with zero mean of a certain distributional trans formal ion. We provide the first rates of convergence for the distribution of Y-n to that of F, using various metrics. In particular, we establish the bound 2n(-1/2) in the d(2)-metric, and the rate O(n(epsilon-(1/2))) for Kolmogorov-Smirnov distance, for any positive (C) 2002 Elsevier Science (USA). All rights reserved.