A Theorem in the Theory of Compromise Merge Methods
Pieter S. Kritzinger, J. Wesley Graham · Journal of the ACM · 1974
Let r be the total number of cycles required to complete a compromise merge of a given number of initial strings. Define row vectors m r - j and d j whose components represent the number and length respectively of strings at the end of the j th 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.