Joint Applied Mathematics and Statistics Colloquium

Title: A local limit theorem for QuickSort key comparisons via multi-round smoothing

Abstract: It is a well-known result, due independently to Régnier (1989) and Rösler (1991), that 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.  We resolve an open problem of Fill and Janson from 2002 by using a multi-round smoothing technique to establish the corresponding local limit theorem.