In-Place Merging Algorithms

In this report we consider the problem of merging two sorted lists of m and n keys each in-place. We survey known techniques for this problem, focussing on correctness and the attributes of Stability and Practicality. We demonstrate a class of unstable in-place merge algorithms that uses block rearrangement and internal buffering that actually does not merge in the presence of sufficient duplicate keys of a given value. We show four relatively simple block sorting techniques that can be used to correct these algorithms. In addition, we show relatively simple and robust techniques that does stable local block merge followed by stable block sort to create a merge. Our internal merge is base on Kronrod’s method of internal buffering and block partitioning. Using block size of O ( √ m + n) we achieve complexity of no more than 1.5(m+n)+O ( √ m + n lg(m+n)) comparisons and 4(m+n)+O ( √ m + n lg(m+n)) data moves. Using block size of O((m + n) / lg(m + n)) gives complexity of no more tha