How heap sort works
- Read the array as a binary tree: the children of position i are at positions 2i + 1 and 2i + 2.
- Build a max heap. Start at the last parent and work back to the root, pushing each value down until it is at least as large as both of its children.
- The root now holds the largest value. Swap it with the last value of the heap and make the heap one value shorter.
- Push the new root down to repair the heap. Repeat until the heap is empty.
What the colours mean
The tree under the bars is the same array drawn as a heap. Black is the largest value found so far among a parent and its children, yellow is the value compared with it, and pink is a swap. Green values have left the heap and are final. In the tree their links are dashed.
Heap Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Building the heap takes O(n), and each of the n removals costs up to log n steps, so heap sort is O(n log n) on every input. A sorted array gives it no shortcut, because the heap has to be built and taken apart either way.
The heap lives in the array being sorted, so no second array is needed. Heapify() is recursive here, which puts up to log n calls on the stack. A loop version needs no stack at all.
The C# code
The listing beside the bars is the SortArray() and Heapify() methods from Heap Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is heap sort stable?
No. Swapping the root with the last value of the heap moves it past everything in between, including values equal to it.
Why does heap sort start building at size / 2 - 1?
That is the position of the last value that has a child. Everything after it is a leaf, and a leaf is already a valid heap of one value.
Does heap sort need extra memory?
It needs no second array. The heap lives in the same array as the data, and the sorted values fill it from the right as the heap shrinks. The recursive Heapify() in this code does use the call stack, up to log n calls deep.