一种同步原地二路归并算法

摘要：

介绍了一种同步原地二路归并算法.通过加入同步策略,该算法优化了内部缓冲区的使用,进一步降低了线性原地二路归并算法的线性系数.归并长度分别为m和n的2个有序子表(m≤n),该算法不超过2.5m+n+2.5√m+2√m lb m次元素比较和5m+3n+6√m+12√mlb m次元素移动.实验证明,与经典原地二路归并排序相比较,该同步原地二路归并算法能够极大地降低元素移动次数和算法的运行时间.

关键词：原地、二路归并、同步、内部缓冲

所属期刊栏目：19

分类号：TP311(计算技术、计算机技术)

资助基金：重庆市教委资助项目2005.78;重庆邮电大学校科研和教改项目2005-18

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

页数：共4页

页码：725-728