A variant of Heapsort—named Ultimate Heapsort—is presented that sorts n elements in-place in Θ(n log₂(n + 1)) worst-case time by performing at most n log₂ n + Θ(n) key comparisons and n log₂ 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.

@inproceedings{Kat1998C,
  author = {Jyrki Katajainen},
  title = {The Ultimate Heapsort},
  booktitle = {Proceedings of the Computing: {T}he 4th Australasian Theory
    Symposium},
  series = {Australian Computer Science Communications},
  volume = {20},
  number = {3},
  publisher = {Springer-Verlag Singapore Pte. Ltd.},
  year = {1998},
  pages = {87--96},
}