AbstractTwo in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log2N+O(N) comparisons and 3Nlog2 N+O(N) moves to sort N elements. The second, more advanced variant requires at most Nlog2N+O(N) comparisons and epsilonNlog2N moves, for any fixed epsilon > 0 and any N > N(epsilon). In theory, the second one is superior to advanced versions of heapsort. In practice, due to the overhead in the index manipulation, our fastest in-place mergesort behaves still about 50 per cent slower than the bottom-up heapsort. However, our implementations are practical compared to mergesort algorithms based on in-place merging.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: sorting, mergesort, in-place algorithms
Selected references
- F. K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM Journal on Computing, 1(1):31-39, March 1972.
- J. Ian Munro and Venkatesh Raman. Sorting with minimum data movement. Journal of Algorithms, 13(3):374-393, September 1992.
- Luis Trabb Pardo. Stable sorting and merging with optimal space and time bounds. SIAM Journal on Computing, 6(2):351-372, June 1977.
- Jeffrey Salowe and William Steiger. Simplified stable merging tasks. Journal of Algorithms, 8(4):557-571, December 1987.
- Russel Schaffer and Robert Sedgewick. The analysis of Heapsort. Journal of Algorithms, 15(1):76-100, July 1993.
- Ingo Wegener. BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT, beating, on an average, QUICKSORT (if n is not very small). Theoretical Computer Science, 118(1):81-98, 13 September 1993.