Heapsort is a comparison-based sorting algorithm that works in two phases. First it arranges the input array into a binary heap, a tree-shaped structure in which every parent is at least as large as its children, so the largest element sits at the root. Then it repeatedly swaps the root to the end of the array and restores the heap property on the shrinking remainder, leaving the elements sorted in place.
The algorithm was introduced by J. W. J. Williams in 1964 as “Algorithm 232: Heapsort,” published in the Communications of the ACM, where he also introduced the binary heap itself. Donald Knuth later analyzed it in “The Art of Computer Programming,” and it is a standard topic in modern courses; the MIT 6.006 lecture notes on heaps and heap sort present the build-heap and extract-max steps and their costs.
Heapsort runs in O(n log n) time in the worst case, because building the heap is linear and each of the n extractions costs at most logarithmic time to restore the heap. It is also in-place, needing only a constant amount of extra memory, which is its main advantage over merge sort. Unlike quicksort, it has no bad inputs that degrade it to quadratic time.
In practice heapsort is often slower than a well-tuned quicksort despite the same asymptotic bound, because its access pattern jumps around the array and interacts poorly with CPU caches. It remains valuable where guaranteed worst-case performance and bounded memory matter, and the underlying heap structure is itself widely used to implement priority queues.