Access Restriction

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

   Open content in new tab
Source: ACM Digital Library