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
in the Zolotarev metric. This implies
several
estimates for other distances and local
approximation results as for characteristic functions, for density
approximation and for the integrated distance of the distribution
functions.
With similar techniques we identify the rates of convergence for the
depth of a random node and the distance of two randomly selected nodes
in a random binary search tree (after normalization) to be both of the
order
in the Zolotarev metric.