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