Limit theorems for mergesort
✍
Hsien-Kuei Hwang
📂
Article
📅
1996
🏛
John Wiley and Sons
🌐
English
⚖ 669 KB
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 probab