| Practical in-place mergesort | |
| Authors: | Jyrki Katajainen, Tomi Pasanen, and Jukka Teuhola |
| Published in: | Nordic Journal of Computing 3,1 (1996), 27-40 |
| Full text: |  PS (152 kB) |
| Copyright: | © Publishing Association Nordic Journal of Computing |
| Abstract: | Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log2 N + O(N) comparisons and 3 N log2 N + O(N) moves to sort N elements. The second, more advanced variant requires at most N log2 N + O(N) comparisons and ε N log2 N moves, for any fixed ε > 0 and any N > N(ε). 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. |
| Related: |  HTML (Conference paper) |
| BibLATEX: | @article{KPT1996J,
author = {Jyrki Katajainen and Tomi Pasanen and Jukka Teuhola},
title = {Practical in-place mergesort},
journaltitle = {Nordic Journal of Computing},
volume = {3},
number = {1},
year = {1996},
pages = {27--40},
}
|