Refined Quicksort asymptotics

Abstract

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 $Y_n$ is known to converge almost surely to a non-degenerate random limit $Y$. This assumes a natural embedding of all $Y_n$ 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: $$\sqrt{\frac{n}{2\log n}}(Y_n-Y)\stackrel{d}{⟶}\mathcal{N}(n\to \infty ),$$ where $\mathcal{N}$ denotes a standard normal random variable.

revised version; title slightly changed; accepted for publication in Random Structures and Algorithms