A Linear-Time In-place Merging Algorithm
一种线性原地二路归并算法

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