摘要
将内部缓冲技术、浮洞技术与分治技术相结合,提出了一种快速线性原地二路归并算法。归并长度分别为m和n的2个有序子表(m≤n),该算法最多需要2.5m+1.5n+4.5m+n次比较和7m+6n-m+n次移动。如进一步降低系数,并与其他好的排序算法有机结合,理论上的原地二路归并算法必将成为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。
By combining the internal buffering technique and the float hole technique with the divide-and-conquer technique, a fast linear-time in-place 2-way merge algorithm is introduced in the paper. The new algorithm needs at most 2.5 m+1.5 n+4.5m+n comparisons and 7 m+6 n-m+n movements to merge two sorted sub-lists of lengths m and n(m≤n).If the coefficients can be marked down and the algorithm can be combined with other fine sort algorithms, the in-place merging algorithm must be converted from a theoretical one into a more practical one than quick-sort algorithm. So the new algorithm has high value in theory and practice.
出处
《重庆邮电学院学报（自然科学版）》
2005年第1期105-108,共4页
Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition)
关键词
原地算法
二路归并
分治法
内部缓冲
浮洞
in-place algorithm
2-way merge
divide-and-conquer
internal buffering
float hole
