An in-place heapsort algorithm requiring nlogn+nlog*n−0.546871n comparisons

Abstract

In this paper, we present an interesting modification to the heap structure which yields a better comparison-based in-place heapsort algorithm. The number of comparisons is shown to be bounded by nlogn+nlog*n−0.546871n which is 0.853129n+nlog*n away from the optimal theoretical bound of nlogn−1.44n.

Keywords:

• algorithms
• data structure
• heapsort

2000 AMS Subject Classifications :

• 68P05
• 68Q25

Acknowledgements

The authors profusely thank anonymous referees for suggesting significant improvement and for pointing out errors and inaccuracies of an earlier version of the manuscript.