一种线性原地二路归并算法

摘要：

和其它排序算法相比,二路归并最适合于两个有序子表的排序.但经典原地二路归并算法的时间性能是乘积型的,尚有改进空间.文章介绍了改进经典原地二路归并算法所需的基本技术,提出了一种线性原地二路归并算法.归并长度分别为m和n的两个有序子表,该算法最多需要2.5m+1.5n+4.5√m+n次比较和8m+7n-3√m+n次移动.

关键词：原地算法、二路归并、块交换、内部缓冲、分块、块排序

所属期刊栏目：31

分类号：TP3;U2

在线出版日期：2005-01-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：221-222,225