Optimizing stable in-place merging

In 2000, Geffert et al. (Theoret. Comput. Sci. 237 (2000) 159) presented an asymptotically efficient algorithm for stable merging in constant extra space. The algorithm requires at most m(1)(t + 1) + m(2)/2' + o(m(1)) comparisons (t = [log(2)(m(2)/m(1))]) and 5m(2) + 12m(1) + o(m(1)) moves, where m(1) and m(2) are the sizes of two ordered sublists to be merged, and in m(1) less than or equal to m(2). This paper optimizes the algorithm. The optimized algorithm is simpler than their algorithm, and makes at most m(1)(t + 1) + m(2)/2' + o(m(1) + m(2)) comparisons and 6m(2) + 7m(1) + o(m(1) + m(2)) Moves. (C) 2002 Elsevier Science B.V. All rights reserved.