Heapsort

In short: Heapsort sorts by turning the data into a max-heap and then repeatedly moving the largest element to the end.

In more detail: It always runs in O(n log n), even in the worst case, and needs no extra memory. In practice it is usually slower than quicksort, though, because it reads memory in jumps rather than linearly.

In Depth

• Step 1: The array is turned into a max-heap in O(n): from the middle backwards, each node is “sifted down”.
• Step 2: The root (largest element) is swapped with the last element. The heap shrinks by 1 and the new root is sifted down.
• Repeat until the heap is empty. The array is then sorted ascending.
• Properties: not stable, in place, independent of presortedness.
• Use: As the fallback in introsort if quicksort recurses too deeply. Compare heap and priority queue.

See also: Merge sort