Heap Sort

Merge sort guarantees O(n log n) but needs O(n) extra space. Heap sort gets the same guaranteed O(n log n) bound in place, O(1) extra space, by reusing the binary heap operations already covered in module 3.

Idea

Each extraction moves the current maximum to the end of the array, one position at a time. As the heap shrinks from the front, the sorted part of the array grows from the back.

Algorithm

HEAP_SORT(A, N)
// A is the array to sort
// N is the number of elements in A
 
1. BUILD_HEAP(A, N)
2. For i = N-1 down to 1:
       Swap A[0] and A[i]
       HEAPIFY_DOWN(A, i, 0)
3. Stop.

BUILD_HEAP and HEAPIFY_DOWN are the exact same operations from binary heap, repeated here for reference:

BUILD_HEAP(A, N)
// A is the array to build into a heap
// N is the number of elements in A
 
1. i = floor(N/2) - 1   // last internal node, zero-based
2. While i >= 0:
       HEAPIFY_DOWN(A, N, i)
       i = i - 1
3. Return

HEAPIFY_DOWN(A, N, i)
// A is the heap array
// N is the current heap size
// i is the index to fix
 
1. LEFT = 2i + 1
2. RIGHT = 2i + 2
3. LARGEST = i
4. If LEFT < N AND A[LEFT] > A[LARGEST]:
       LARGEST = LEFT
5. If RIGHT < N AND A[RIGHT] > A[LARGEST]:
       LARGEST = RIGHT
6. If LARGEST == i:
       Return
7. Swap A[i] and A[LARGEST]
8. HEAPIFY_DOWN(A, N, LARGEST)

Worked example

Sorting [4, 10, 3, 5, 1] in ascending order.

Phase 1: build a max heap

Starting array as a tree (not yet a heap):

The last internal node is at index floor(5/2)-1 = 1 (10). Heapify from there upward:

Heapify at index 1 (10): children are 5 and 1, both smaller than 10, already a valid max-heap locally, no change.

Heapify at index 0 (4): children are 10 and 3. Larger child is 10, and 10 > 4, swap:

Continue heapify-down from the new position of 4 (index 1): children 5 and 1, larger child 5 > 4, swap:

Max heap built.

Phase 2: repeated extraction

Extract 1: swap root (10) with the last element (1), shrink heap size to 4, heapify-down:

Heapify-down 1 at the root: children 5 and 3, larger is 5, swap:

1 (now index 1) has one child, 4, and 4 > 1, swap again:

Extract 2: swap root (5) with the last unsorted element (index 3, 1), shrink to size 3, heapify-down:

Heapify-down 1: children 4 and 3, larger is 4, swap:

Extract 3: swap root (4) with last unsorted element (index 2, 3), shrink to size 2:

Heapify-down 3: only child is 1, 1 < 3, no swap needed.

Extract 4: swap root (3) with last unsorted element (index 1, 1):

Heap size is now 1, nothing left to extract. Sorted.

Complexity

Heap sort vs merge sort vs quick sort

Quick recall

• Build a max heap from the whole array (O(n)), then repeatedly swap the root with the last unsorted element and heapify-down, growing a sorted suffix from the back.
• Reuses binary heap's bottom-up build and heapify-down directly, no new operations.
• O(n log n) guaranteed in every case; O(1) extra space (in-place); not stable.
• Trades merge sort's stability and quick sort's typical speed for guaranteed in-place O(n log n).