A simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT

McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which r equires nlog(2)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 anal yzed the average and worst case complexity of the algorithm which is very c omplex 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 sh ow that it requires nlog(2)n + n element comparisons in the worst case and nlog(2)n + 0.42n comparisons on the average.