Heap sort
Heap sort first arranges the array into a max-heap: a binary tree stored in the array itself, where every parent is at least as large as its children. It then repeatedly swaps the root — the largest remaining value — with the last unsorted position, and restores the heap property on the shrunken heap.
When it is the right choice
Heap sort is the right choice when a guaranteed O(n log n) worst case and O(1) extra space both matter, such as in memory-constrained settings, since unlike quicksort it has no input that makes it degrade and unlike merge sort it needs no auxiliary buffer. It is rarely chosen otherwise, because its constant factors make it slower in practice than a well-implemented quicksort, and it is not stable.
How it works
- Build a max-heap by sifting every parent down, starting from the middle of the array and working back to the start.
- To sift a value down, compare it with its largest child to see which is bigger.
- If a child is larger than its parent, swap them and keep sifting the value down from its new position.
- Once the heap is built, repeatedly swap the root (the largest remaining value) with the last value in the heap, then shrink the heap by one.
- Sift the new root back down to restore the max-heap property before repeating.
Worth noticing
- It is not stable: the heap operations can swap an equal element past another equal element.
- Its comparisons and swaps have a larger constant factor than quicksort's, so despite a better worst case it is usually slower in practice.
- The array being sorted is also the heap itself — there is no second data structure, which can make the intermediate states look less orderly than a separate heap diagram would.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Extra space
- O(1)
- Stable
- No