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

A synchronous in-place 2-way merge algorithm

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

A synchronous in-place 2-way merge algorithm is introduced, The use of the internal buffers is optimized by introducing synchronous strategy and the coefficients of linear-time in place 2 way merge algorithms are reduced. The synchronous algorithm needs no more than 2.5m＋n＋2.5√＋2√m 1b m comparisons and 5m＋3n＋6√m＋12√m1bm movements to merge two sorted sublists of lengths m and n（m≤n）. The experiment certifies that the assignments and run-time of the synchronous algorithm can be reduced enormously compared with the classic inplace 2 way merge sort algorithm.