Limit theorems for mergesort
Hsien‐Kuei Hwang · Random Structures and Algorithms · 1996
Central and local limit theorems (including large deviations) are established for the number of comparisons used by the standard top-down recursive mergesort under the uniform permutation model. The method of proof utilizes Dirichlet series, Mellin transforms, and standard analytic methods in probability theory. © 1996 John Wiley & Sons, Inc.