STOCHASTIC-ANALYSIS OF THE MERGE-SORT ALGORITHM

Authors
Citation
M. Cramer, STOCHASTIC-ANALYSIS OF THE MERGE-SORT ALGORITHM, Random structures & algorithms, 11(1), 1997, pp. 81-96
Citations number
7
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
ISSN journal
10429832
Volume
11
Issue
1
Year of publication
1997
Pages
81 - 96
Database
ISI
SICI code
1042-9832(1997)11:1<81:SOTMA>2.0.ZU;2-I
Abstract
The number L-k of comparisons performed by the Merge-Sort algorithm to sort 2(k) keys follows the recursion L-k(d) = Lk-1 + <(Lk-1)over bar> + Y-k, where Lk-1, <(Lk-1)over bar>, and Y-k are independent and <(Lk -1)over bar> is a copy of Lk-1. The contraction method for ideal metri cs of Rachev and Ruschendorf [7] is appropriate to handle recursions o f the above type and to show asymptotic normality of the normalized L- k. Additional challenges have to be faced if the number of keys is not a power of 2. The difficulty lies in the fact that the cases of odd a nd even numbers differ slightly. Therefore, exact calculations of mean and variance have to be substituted by asymptotic results which are g ained with the help of a run of a C-program. But even in that case asy mptotic normality can be achieved by a refinement of the contraction p rinciple. (C) 1997 John Wiley & Sons, Inc.