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.