UnfairDuelMerge: Merging with Even Fewer Moves. (16th March 2019)
- Record Type:
- Journal Article
- Title:
- UnfairDuelMerge: Merging with Even Fewer Moves. (16th March 2019)
- Main Title:
- UnfairDuelMerge: Merging with Even Fewer Moves
- Authors:
- Mergen, Sergio L S
- 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.
- Is Part Of:
- Computer journal. Volume 63:Number 5(2020)
- Journal:
- Computer journal
- Issue:
- Volume 63:Number 5(2020)
- Issue Display:
- Volume 63, Issue 5 (2020)
- Year:
- 2020
- Volume:
- 63
- Issue:
- 5
- Issue Sort Value:
- 2020-0063-0005-0000
- Page Start:
- 701
- Page End:
- 708
- Publication Date:
- 2019-03-16
- Subjects:
- array merging -- algorithms
Computers -- Periodicals
005.1 - Journal URLs:
- http://comjnl.oxfordjournals.org/ ↗
http://ukcatalogue.oup.com/ ↗ - DOI:
- 10.1093/comjnl/bxz015 ↗
- Languages:
- English
- ISSNs:
- 0010-4620
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.060000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 15063.xml