STOCHASTIC-ANALYSIS OF SIMULTANEOUS MERGE-SORT

The asymptotic behaviour of the recursion M-k =(d) Mk-1 boolean OR <(M k-1)over bar> + Y-k is investigated; Y-k describes the number of compa risons which have to be carried out to merge two sorted subsequences o f length 2(k-1) and M-k can be interpreted as the number of comparison s of 'Simultaneous Merge-Sort'. The challenging problem in the analysi s of the above recursion lies in the fact that it contains a maximum a s well as a sum. This demands different ideal properties for the metri c in the contraction method. By use of the weighted Kolmogorov metric it is shown that an exponential normalization provides the recursion's convergence. Furthermore, one can show that any sequence of linear no rmalizations of M-k must converge towards a constant if it converges i n distribution at all.