SortingSorting

Heap Sort

Build a max-heap in place, then repeatedly swap the root to the end and restore the heap.

Learn Heap Sort →
a
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
heap (array view, size 8)
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/45Start with 8 elements. Heap sort first turns the array into a max-heap in place (a[i]'s children are a[2i+1] and a[2i+2]), then repeatedly extracts the maximum.
Node being siftedChildren comparedSwappedExtracted (final position)
PseudocodeLearn Heap Sort →
1for i in n//2-1 .. 0: siftDown(a, i, n)   # build max-heap
2for end in n-1 .. 1:
3  swap(a[0], a[end])   # move max to the end
4  siftDown(a, 0, end)
5siftDown(a, i, size):
6  while 2i+1 < size:
7    child = larger of 2i+1, 2i+2
8    if a[i] >= a[child]: break
9    swap(a[i], a[child]); i = child
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(1)
Speed