### Optimum combinations of sorting and mergingOptimum combinations of sorting and merging

Access Restriction
Subscribed

 Author Manacher, G. K. ♦ Bui, T. D. ♦ Mai, T. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1989 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on $\textit{t}$ real numbers, can be beaten for an infinite set of values $\textit{t}.$ These values form a partial cover of constant density not close to 1 over an initial sequence of each $\textit{band}$ running from $\textit{uk}$ = ⌊(4/3)2k⌋ to $\textit{uk}+l$ - 1. This early result depended on showing that the Hwang-Lin merging algorithm [HLA], merging $\textit{m}$ elements with $\textit{n},$ $\textit{m}$ ≠ $\textit{n},$ could be surpassed by $\textit{cm}$ comparisons, where $\textit{c}$ is an arbitrary small positive constant.In this paper, it is shown that the FJA can be beaten for a set of integers of asymptotic density 1 under the greatly weakened assumption that the HLA can be surpassed by only (1/2 + ε)log $\textit{m}$ comparisons, with ε a small positive constant. The even weaker assumption that $\textit{no}$ improvement in the HLA exists, but that an isolated value $\textit{t}o$ exists for which the FJA can be surpassed by only (1 + ε)log $\textit{t}o$ comparisons yields the same result. Only for a set of “refractory” integers of size about $\textit{t}1/2$ in the neighborhood of each $\textit{uk}$ does the FJA fail to be beaten.All these results depend on a new technique for obtaining optimum sort-merge sequences for best-possible sorting given a merging method. The technique turns out to be amenable to precise asymptotic analysis. When the technique is applied using the most powerful known merging algorithm [Christen's], the density mentioned above is still 1, but islands of refractory points still remain, this time forming sets provably of size $&THgr;(log2\textit{t})$ in the neighborhood of each $\textit{uk}.It$ is shown that if “information theoretic” merging were achievable, the FJA could be beaten for all $\textit{t}$ > $\textit{u}10$ = 1365. From these results and a few others, we adduce evidence in support of our main conjecture: that even $\textit{optimum}$ combinations of $\textit{optimum}$ merging and Ford-Johnson sorting will not beat the FJA when $\textit{t}$ = $\textit{uk},$ but will instead produce refractory regions of size $&THgr;(log2\textit{t})$ in the neighborhood of each $\textit{λ}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1989-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 36 Issue Number 2 Page Count 45 Starting Page 290 Ending Page 334

#### Open content in new tab

Source: ACM Digital Library