A synchronous in-place 2-way merge algorithm
HE Xian-gang · Journal of Chongqing University of Posts and Telecommunications · 2007
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.5m+2mlb m comparisons and 5m+3n+6m+12mlb m 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 in-place 2-way merge sort algorithm.