On the Optimality of Linear Merge

Abstract

Let $M(m,n)$ be the minimum number of pairwise comparisons which will always suffice to merge two linearly ordered lists of lengths m and n. We prove that $M(m,m + d) = 2m + d - 1$ whenever $m \geqq 2d - 2$. This generalizes earlier results of Graham and Karp $(d = 1)$, Hwang and Lin $(d = 2,3)$, Knuth $(d = 4)$, and shows that the standard linear merging algorithm is optimal whenever $m \leqq n \leqq \lfloor 3m/2 \rfloor + 1$.