Mellin Transforms and Asymptotics: The Mergesort Recurrence

Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide--and--conquer algorithms. This lecture illustrates the techniques by providing a precise analysis of the standard top--down recursive mergesort algorithm, in the average--case as well as in the worst--case. We also derive the variance and show that the cost of mergesort has a Gaussian limiting distribution. The approach is applicable to a number of divide--and--conquer recurrences related to sorting networks, fast multiplication, maxima finding and multidimensional divide--and--conquer recurrences. (Joint work with Ph. Flajolet)