STOCHASTIC-ANALYSIS OF THE MERGE-SORT ALGORITHM

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.