A Fast In-place Merging Algorithm on the Basis of Dividing Data into Blocks
Fan Shi · 2004
Comparing with other sorting algorithms,the 2-merge algorithm is the best one to sort two sorted sublist- s.We have two classic algorithms to merge two sorted sublists A and B of lengths m and n.The first algorithm needs ○(m+n)additional space,○(m+n)comparisons and(○m+n)assignments.The second algorithm is in-place and needs ○(m+n)comparisons and ○(m+n)assignments.After long study,a fast in-place merging algorithm on the basis of dividing data into blocks is introduced.The new algorithm at most needs ○((m+n)log_2√(m+n)))compar- isons and ○((m+n)~(3/2))assignments to merge two sorted sublists in-place by dividing the data into blocks and sorting the data blocks,etc.Comparing with the classic in-place algorithm,the experiments certify that the new algorithm re- duces assignments and run time enormously.