Asymptotically efficient in-place merging

Two linear-time algorithms for in-place merging are presented. Both algorithms perform at most m(t + 1) + n/2(t) + o(m) comparisons, where m and n are the sizes of the input sequences, m less than or equal to n, and t = [log(2)(n/m)]. The first algorithm is for unstable merging and it carries out no more than 3(n + m) + o(m) element moves. The second algorithm is for stable merging and it accomplishes at most 5n + 12m + o(m) moves. (C) 2000 Elsevier Science B.V. All rights reserved.