A Class of Merging Algorithms

ABSTRACT

Suppose we are given two disjoint linearly ordered subsets A and B of a linearly ordered set C, say A = {a1 < a2 < ··· < am} and B = {b1 < b2 < ··· < bn}. 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 Ks(m, n) required under all possible orderings of A ∪ B. An algorithm s is said to be minimax if Ks(m, n) = K(m, n) where K(m, n) = mins Ks(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.

REFERENCES

• 1: GRAHAM, R.L. Unpublished manuscript.
• 2: HWANG, :F. K., AND LIN, S. An optimal algorithm for merging an ordered set of length two with another ordered set. Acta Inforraatica 1,2 (1971), 145-158.
• 3: HW~NG, F K., AND LIN, S. A simple algorithm for merging two disjoint linearly-ordered sets. SIAM J. Comp. 1, 1 (1972), 31-39.
• 4: SANDELIUS, M. Onanoptimalsearchprocedure. Amer. Math. Monthly68,2 (1961),133-134.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Measurement, Performance, Theory, Verification