A simple shuffle-based stable in-place merge algorithm

Sorting is one of the most fundamental problems in computer science. Divide-and-conquer based sorting algorithms use successive merging to combine sorted arrays; therefore performance of merging is critical for these types of applications. The classic merge algorithm uses an extra O(m+n) memory for combining arrays of size m and n. Some improvements on merge algorithms include in-place methods which reduce or eliminate additional memory space, thus getting more practical value. We present a new in-place, stable and shuffle-based merge algorithm which is simple to understand and program. The algorithm starts applying perfect shuffle on two sorted arrays. Then, using the knowledge that odd and even-indexed numbers are sorted among themselves, comparisons are made and then misplaced elements are relocated by applying successive inverse perfect shuffle and swap operations on blocks. We have implemented and compared the new algorithm with the classical merge algorithm and the shuffle-based algorithm of Ellis and Markov (Comp. J. 1(2000)). Through experiments we have observed that the new algorithm exhibits linear run time behaviour and has dramatic performance improvement compared to the Ellis and Markov's algorithm [1]. (C) 2010 Published by Elsevier Ltd. Selection and/or peer-review under responsibility of the Guest Editor.