Joint Applied Mathematics and Statistics Colloquium
Dr. Jim Fill, The Johns Hopkins University
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.This is joint work with Béla Bollobás and Oliver Riordan.