We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DuelMerge: Merging with Fewer Moves.
- Authors
MERGEN, SERGIO L. S.; MOREIRA, VIVIANE P.
- Abstract
This work proposes DUELMERGE, a stable merging algorithm that is asymptotically optimal in the number of comparisons and performs O (n log2 (n) moves. Unlike other partition-based algorithms, we only allow blocks of equal sizes to be swapped, which reduces the number of moves required. We performed experiments comparing DUELMERGE against a number of baselines including RECMERGE, the standard merging solution for programming languages such as C, and some more recent approaches. The results show that our proposed algorithm performs fewer moves than other stable solutions. Experiments employing DUELMERGE within MergeSort confirmed our positive results in terms of moves, comparisons and runtime.
- Subjects
COMPUTER algorithms; PSEUDOCODE (Computer program language); C (Computer program language); PROGRAMMING languages; COMPUTER science
- Publication
Computer Journal, 2017, Vol 60, Issue 9, p1271
- ISSN
0010-4620
- Publication type
Article
- DOI
10.1093/comjnl/bxw105