Name
Abstract | ||
|---|---|---|
Queue-mergesort is recently introduced by Golin and Sedgewick as an optimal variant of mergesorts in the worst case. In this paper, we present a complete analysis of the cost distribution of queue-mergesort, including the best, average and variance cases. The asymptotic normality of its cost is also established under the uniform permutation model. We address the corresponding optimality problems and show that if we x the merging scheme then the optimal mergesort as far as the average number of comparisons is concerned is to 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 latter property. A comparative discussion is given on the probabilistic behaviors of top-down mergesort, bottom-up mergesort and queue-mergesort. We derive an \invariance principle" for asymptotic linearity of divide-and-conquer recurrences based on general \power-of-two" rules of which the underlying dividing rule of queue-mergesort is a special case. These analyses reveal an interesting algorithmic feature for general \power-of-two" rules. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1006/jagm.1998.0986 | Journal of Algorithms |
Keywords | Field | DocType |
power-of-2 rule,cost distribution,optimal mergesorts,divide and conquer,optimization problem,invariance principle,bottom up,top down | Mathematical optimization,Combinatorics,Merge sort,Permutation,Queue,Sorting,Probabilistic logic,Mathematics,Recursion,Asymptotic distribution,Special case | Journal |
Volume | Issue | ISSN |
30 | 2 | 0196-6774 |
Citations | PageRank | References |
6 | 0.56 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei‐Mei Chen | 1 | 57 | 9.26 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |
| guihai chen | 3 | 3537 | 317.28 |