UnfairDuelMerge: Merging with Even Fewer Moves. (16th March 2019)

• Record Type: Journal Article
• Authors: Mergen, Sergio L S
• Is Part Of: Computer journal. Volume 63:Number 5(2020)
• Page Start: 701
• Page End: 708
• Publication Date: 2019-03-16
• Subjects: array merging -- algorithms; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz015
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The merging problem consists of forming an ordered sequence with n elements from two ordered sequences with n 1 and n 2 elements (where n = n 1 + n 2 ). One recent development in in-place merging is a minimum storage algorithm (DuelMerge) that requires half the number of moves in average, when compared to other partition-based algorithms. The reduction is achieved by limiting the exchange to blocks with equal sizes, and using a particularly suited exchange method. The algorithm proposed in this paper (UnfairDuelMerge) reduces the number of moves even further, by limiting the exchange to blocks where the left side is one element larger than the right side, and using the floating hole technique to perform the exchange. As its predecessor, the algorithm is stable, in-place and the merge is asymptotically performed with a O ( n log n n ) runtime. A formal description of the method is provided, as well as an analysis of stability, memory cost and time complexity. Experimental results show that the proposed algorithm outperforms other partition-based solutions when applied directly to merge ordered sequences and when used within MergeSort.