Heapsort

An $N\lg N$ Sorting Algorithm which is not quite as fast as Quicksort. It is a ``sort-in-place'' algorithm and requires no auxiliary storage, which makes it particularly concise and elegant to implement.

See also Quicksort, Sorting

References

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Heapsort.'' §8.3 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 327-329, 1992.