# MPI-I-91-104

## A tight lower bound for the worst case of bottom-up-heapsort

### Fleischer, Rudolf

**MPI-I-91-104**. April** **1991, 13 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Bottom-Up-Heapsort is a variant of Heapsort.

Its worst case complexity for the number of comparisons

is known to be bounded from above by ${3\over2}n\log n+O(n)$, where $n$

is the number of elements to be sorted.

There is also an example of a heap which needs ${5\over4}n\log n-

O(n\log\log n)$ comparisons.

We show in this paper that the upper bound is asymptotical tight,

i.e.~we prove for large $n$ the existence of heaps which need at least

$c_n\cdot({3\over2}n\log n-O(n\log\log n))$ comparisons

where $c_n=1-{1\over\log^2n}$ converges to 1.

This result also proves the old conjecture that the best case

for classical Heapsort needs only asymptotical $n\log n+O(n\log\log n)$

comparisons.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 23 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-104

**BibTeX**
`@TECHREPORT{``Fleischer91``,`

` AUTHOR = {Fleischer, Rudolf},`

` TITLE = {A tight lower bound for the worst case of bottom-up-heapsort},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-91-104},`

` MONTH = {April},`

` YEAR = {1991},`

` ISSN = {0946-011X},`

`}`