2017/01/16 by Béla Bollobás, Bollobás, Béla, James Allen Fill +3
Computer Science · Mathematics · #60C05 #60F05 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Limits and Structures in Graph Theory #Primary 68W40 #Probability (math.PR) #secondary 68P10
paper · pdf · doi:10.48550/arxiv.1701.04365
openalex publication_date 2017/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.