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.gif>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.gif>HTML (Conference paper)  
  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},
This page was generated by Jyrki Katajainen <> on 16.01.2014.