OPTIMAL STABLE MERGING

This paper shows how to stably merge two sequences A and B of sizes m and n, m less than or equal to n, respectively, with O(m + n) assignme nts, O(mlog(n/m + 1)) comparisons and using only a constant amount of additional space. This result matches all known lower bounds and close s an open problem posed by Dudzinski and Dydek in 1981. Our algorithm is based on the unstable algorithm of Mannila and Ukkonen. All techniq ues we use have appeared in the literature in more complicated forms b ut were never combined together. They are powerful enough to make stab le all the existing linear in-place unstable algorithms we are aware o f. We also present a stable algorithm that requires a linear number of comparisons and assignments which we consider to be the simplest algo rithm for in-place merging.