The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2 rules

Queue-mergesort is introduced by Golin and Sedgewick as an optimal variant of mergesorts in the worst case. In this paper, we present a complete analy sis of the cost distribution of queue-mergesort, including the best, averag e, and variance cases. The asymptotic normality of its cost is also establi shed under the uniform permutation model. We address the corresponding opti mality problems and we show that if we fix the merging scheme then the opti mal mergesort as far as the average number of comparisons is concerned is t o divide as evenly as possible at each recursive stage (top-down mergesort) . On the other hand, the variance of queue-mergesort reaches asymptotically the minimum value. We also characterize a class of mergesorts with the lat ter property. A comparative discussion is given on the probabilistic behavi ors of top-down mergesort, bottom-up mergesort, and queue-mergesort. We der ive an "invariance principle" for asymptotic linearity of divide-and-conque r recurrences based on general "power-of-2" rules of which the underlying d ividing rule of queue-mergesort is a special case. These analyses reveal an interesting algorithmic feature for general power-of-2 rules. (C) 1999 Aca demic Press.