Refined quicksort asymptotics
The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of n data, permuted uniformly at random, the appropriately normalized complexity Yn is known to converge almost surely to a non-degenerate random limit Y. This assumes a natural embedding of all Yn on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown:
quicksort complexity key comparisons central limit theorem strong limit theorem rate of convergence zolotarev metric contraction method