一种基于数据块交换的快速稳定原地归并算法

A fast stable in-place merging algorithm based on swapping data blocks

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。

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.