A fast stable in-place merging algorithm based on swapping data blocks
Linlin Wang · Journal of Chongqing University of Posts and Telecommunications · 2004
Compared with other sorting algorithms ,the 2-way merge algorithm is the best one for sorting two sorted sublists. There are two classical algorithms to merge two sorted sublists of lengths m and n. The first algorithm needs O(m+n) additional space,O(m+n) comparison and O(m+n) movements. The second algorithm is in-place and needs O(m+n) comparison and O(m×n) movements. A fast stable in-place merging algorithm on the basis of swapping data blocks is introduced in the paper.The experiments certify that the new algorithm reduces the movements of the former in-place algoritm enormously.