The normalized number of key comparisons needed to sort a list of randomly permuted items by the Quicksort algorithm is known to converge in distribution. We identify the rate of convergence to be of the order Θ (ln(n)/n) in the Zolotarev metric. This implies several ln(n)/n estimates for other distances and local approximation results as for characteristic functions, for density approximation, and for the integrated distance of the distribution functions.
['Ralph Neininger', 'Ludger Rüschendorf']
Rates of convergence for Quicksort