Approximating the limiting quicksort distribution

The limiting distribution of the normalized number of comparisons used by Q uicksort to sort an array of n numbers is known to be the unique fixed poin t with zero mean of a certain distributional transformation S. We study the convergence to the limiting distribution of the sequence of distributions obtained by iterating the transformation S. beginning with a (nearly) arbit rary starting distribution. We demonstrate geometrically fast convergence f or various metrics and discuss some implications for numerical calculations of the limiting Quicksort distribution. Finally, we give companion lower b ounds which show that the convergence is not faster than geometric. (C) 200 1 John Wiley & Sons, Inc.