A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
Rezaul Chowdhury, Mohammad Kaykobad, Suman Kumar Nath · International Journal of Computer Mathematics · 2000
McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog2 n+n element comparisons (for n= 2 h+1-1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n= 2 h+1-1, we show that it requires nlog2 n+n element comparisons in the worst case and nlog2 n+0.42n comparisons on the average