Stochastic analysis of ‘simultaneous merge–sort’

Stochastic analysis of ‘simultaneous merge–sort’

0.00 Avg rating0 Votes
Article ID: iaor19983123
Country: United Kingdom
Volume: 29
Issue: 3
Start Page Number: 669
End Page Number: 694
Publication Date: Sep 1997
Journal: Advances in Applied Probability
Authors:
Keywords: computational analysis
Abstract:

The asymptotic behaviour of the recursion Mk=dMk–1Mk–1 + Yk is investigated; Yk describes the number of comparisons which have to be carried out to merge two sorted subsequences of length 2k–1 and Mk can be interpreted as the number of comparisons of ‘Simultaneous Merge–Sort’. The challenging problem in the analysis of the above recursion lies in the fact that it contains a maximum as well as a sum. This demands different ideal properties for the metric 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 normalizations of Mk must converge towards a constant if it converges in distribution at all.

Reviews

Required fields are marked *. Your email address will not be published.