Premium
Limit theorems for mergesort
Author(s) -
Hwang HsienKuei
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199607)8:4<319::aid-rsa3>3.0.co;2-0
Subject(s) - permutation (music) , limit (mathematics) , mathematics , central limit theorem , dirichlet distribution , large deviations theory , series (stratigraphy) , dirichlet series , merge sort , calculus (dental) , sort , statistics , mathematical analysis , arithmetic , physics , paleontology , acoustics , biology , boundary value problem , medicine , sorting algorithm , dentistry
Abstract 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.