A local limit theorem for Quicksort key comparisons via multi-round smoothing

Abstract

As proved by Régnier and Rösler, the number of key comparisons required by the randomized sorting algorithm QuickSort to sort a list of $n$ distinct items (keys) satisfies a global distributional limit theorem. Fill and Janson proved results about the limiting distribution and the rate of convergence, and used these to prove a result part way towards a corresponding local limit theorem. In this paper we use a multi-round smoothing technique to prove the full local limit theorem.

29 pages

References in corpus (1)

• Counting connected hypergraphs via the probabilistic method