| The Ultimate Heapsort | |
| Author: | Jyrki Katajainen |
| Publication: | Report 96/42, Department of Computer Science, University of Copenhagen (1996), 8 app.pp. |
| Abstract: | A variant of Heapsort—named Ultimate Heapsort—is presented that sorts n elements in-place in Θ(n log2(n + 1)) worst-case time by performing at most n log2 n + Θ(n) key comparisons and n log2 n + Θ(n) element moves. The secret behind Ultimate Heapsort is that it occasionally transforms the heap it operates with to a two-layer heap which keeps small elements at the leaves. Basically Ultimate Heapsort is like Bottom-Up Heapsort, but due to the two-layer heap property an element taken from a leaf has to be moved towards the root only O(1) levels, on an average. |
| Related: |  HTML (Conference version) |
| BibLATEX: | @report{Kat1996cR,
author = {Jyrki Katajainen},
title = {The Ultimate Heapsort},
type = {Report},
number = {96/42},
institution = {Department of Computer Science, University of Copenhagen},
year = {1996},
pagetotal = {8},
}
|