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:
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.