Heap Sort
MediumBuild a max heap in place, then repeatedly swap the root to the end and sift the new root down.
heapin placeO(n log n)
TimeO(n log n)
SpaceO(1)
InputComma separated numbers
4
0
10
1
3
2
5
3
1
4
8
5
Read the array as a complete binary tree: children of i sit at 2i+1 and 2i+2.
comparisons0swaps0
1 / 30
build max heap: for i from n/2-1 down to 0: siftDown(i)
for end from n-1 down to 1:
swap(a[0], a[end])
siftDown(0, end)
siftDown(i, size): move a[i] down while a child is larger
Why it matters
The only comparison sort that is both in place and guaranteed n log n.
Keyboard
space play← → stepr restartctrl K search
More in Heap / Priority Queue
Next visualiser
Counting Sort