A meticulous analysis of mergesort programs
Authors:Jyrki Katajainen and Jesper Larsson Träff
Published in:Proceedings of the 3rd Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science 1203, Springer-Verlag (1997), 217-228
Copyright:© Springer-Verlag

The efficiency of mergesort programs is analysed under a simple unit-cost model. In our analysis the time performance of the sorting programs includes the costs of key comparisons, element moves and address calculations. The goal is to establish the best possible time-bound relative to the model when sorting n integers. By the well-known information-theoretic argument n log2 nO(n) is a lower bound for the integer-sorting problem in our framework. New implementations for two-way and four-way bottom-up mergesort are given, the worst-case complexities of which are shown to be bounded by 5.5 n log2 n + O(n) and 3.25 n log2 n + O(n), respectively. The theoretical findings are backed up with a series of experiments which show the practical relevance of our analysis when implementing library routines for internal-memory computations.

Related:<html.gif>HTML (Technical report)  
  author = {Jyrki Katajainen and Jesper Larsson Tr\"{a}ff},
  title = {A meticulous analysis of mergesort programs},
  booktitle = {Proceedings of the 3rd Italian Conference on Algorithms and
  series = {Lecture Notes in Computer Science},
  volume = {1203},
  publisher = {Springer-Verlag},
  year = {1997},
  pages = {217--228},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.