A Theorem in the Theory of Compromise Merge Methods

ABSTRACT

Let r be the total number of cycles required to complete a compromise merge of a given number of initial strings. Define row vectors mr-j and dj whose components represent the number and length respectively of strings at the end of the jth cycle of the merge. It is shown in this paper that there are asymptotic approximations to these vectors, which enables one to compute their respective components directly. Consequently, the number of cycles r can be computed directly, as in the case of the balanced merge.

REFERENCES

• 1: Donald E. Knuth , Martin A. Goetz, Letters to the editor: three letters on merging, Communications of the ACM, v.6 n.10, p.585, Oct. 1963 [doi>10.1145/367651.367654]
• 2: RADKE, C.E. Merge-Sort Analysis by Matrix Techniques. IBM Syst. Y. 5, 4 (I966), 226-247.
• 3: VAaGA, R. S. Malrix lterative A~zaIysis. Prentice-Hall, Englewood Cliffs, N. J., 1962, p. 31.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

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