|
|
重庆邮电大学学报(自然科学版) 2007
A synchronous in-place 2-way merge algorithm
|
Abstract:
介绍了一种同步原地二路归并算法。通过加入同步策略，该算法优化了内部缓冲区的使用，进一步降低了线性原地二路归并算法的线性系数。归并长度分别为m和n的2个有序子表（m≤n），该算法不超过2.5m＋n＋2.5〖KF(〗m〖KF)〗＋2〖KF(〗m〖KF)〗 lb m次元素比较和5m＋3n＋6〖KF(〗m〖KF)〗＋12〖KF(〗m〖KF)〗lb m次元素移动。实验证明，与经典原地二路归并排序相比较，该同步原地二路归并算法能够极大地降低元素移动次数和算法的运行时间。
