### A Class of Merging AlgorithmsA Class of Merging Algorithms

Access Restriction
Subscribed

 Author Hwang, F. K. ♦ Deutsch, D. N. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1973 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Suppose we are given two disjoint linearly ordered subsets $\textit{A}$ and $\textit{B}$ of a linearly ordered set $\textit{C},$ say $\textit{A}$ = ${\textit{a}1$ < $\textit{a}2$ < ··· < $\textit{am}}$ and $\textit{B}$ = ${\textit{b}1$ < $\textit{b}2$ < ··· < $\textit{bn}}.$ The problem is to determine the linear ordering of their union (i.e. to merge $\textit{A}$ and $\textit{B})$ by means of a sequence of pairwise comparisons between an element of $\textit{A}$ and an element of $\textit{B}$ (which we refer to in the paper as the (m, n) problem). Given any algorithm $\textit{s}$ to solve the (m, n) problem, we are interested in the maximum number of comparisons $\textit{Ks}(\textit{m,$ n) required under all possible orderings of $\textit{A}$ ∪ $\textit{B}.$ An algorithm $\textit{s}$ is said to be minimax if $\textit{Ks}(\textit{m,$ n) = $\textit{K}(\textit{m,$ n) where $\textit{K}(\textit{m,$ n) = mins $\textit{Ks}(\textit{m,$ n)It is a rather difficult task to determine $\textit{K}(\textit{m,$ n) in general. In this study the authors are only concerned with the minimax over a particular class of merging algorithms. This class includes the tape merge algorithm, the simple binary algorithm, and the generalized binary algorithm. 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 1973-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 20 Issue Number 1 Page Count 12 Starting Page 148 Ending Page 159

#### Open content in new tab

Source: ACM Digital Library