A Class of Merging Algorithms
F. K. Hwang, Daniel Deutsch · Journal of the ACM · 1973
Suppose we are given two disjoint linearly ordered subsets A and B of a linearly ordered set C , say A = { a 1 < a 2 < ··· < a m } and B = { b 1 < b 2 < ··· < b n }. The problem is to determine the linear ordering of their union (i.e. to merge A and B ) by means of a sequence of pairwise comparisons between an element of A and an element of B (which we refer to in the paper as the ( m, n ) problem). Given any algorithm s to solve the ( m, n ) problem, we are interested in the maximum number of comparisons K s ( m, n ) required under all possible orderings of A ∪ B . An algorithm s is said to be minimax if K s ( m, n ) = K ( m, n ) where K ( m, n ) = mins K s ( m, n ) It is a rather difficult task to determine K ( 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.