max planck institut
informatik

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

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},