@article {IOPORT.01428267,
    author       = {Chowdhury, Rezaul Alam and Kaykobad, M. and Nath, Suman Kumar},
    title        = {A simplified complexity analysis of McDiarmid and Reed's variant of bottom-up-heapsort.},
    year         = {2000},
    journal      = {International Journal of Computer Mathematics},
    volume       = {73},
    number       = {3},
    issn         = {0020-7160},
    pages        = {293-297},
    publisher    = {Taylor \& Francis, Abingdon},
    doi          = {10.1080/00207160008804896},
    abstract     = {Summary: {\it C. J. H. McDiarmid} and {\it B. A. Reed} [J. Algorithms 10, No. 3, 352-365 (1989; Zbl 0681.68069)] presented a variant of BOTTOM-UP-HEAPSORT which requires $n\log_2n+ n$ element comparisons (for $n= 2^{h+1}-1)$ in the worst case, but requires an extra storage of $n$ bits. {\it I. Wegener} [Inf. Comput. 97, No. 1, 86-96 (1992; Zbl 0766.68025)] has analyzed the average and worst case complexity of the algorithm which is very complex and long. 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 $n\log_2n+ n$ element comparisons in the worst case and $n\log_2n+ 0.42n$ comparisons on the average.},
    identifier   = {01428267},
}