Heap Sort Animation & Pseudocode Walkthrough

Heap sort leverages the structure of a binary heap to continually surface the largest element. The array is first rearranged into a max heap, ensuring every parent is greater than its children. We then repeatedly swap the root with the last unsorted item, shrink the heap, and sift the new root down to restore the heap property. Follow the pseudocode highlights, explanations, and animation to see how the array becomes sorted.

Pseudocode

  1. for index from ⌊n/2⌋ - 1 down to 0:
  2.   call siftDown(array, index, n - 1)
  3. for end from n - 1 down to 1:
  4.   swap array[0] with array[end]
  5.   call siftDown(array, 0, end - 1)
  6. function siftDown(array, root, end):
  7.   while root * 2 + 1 ≤ end:
  8.     let child = root * 2 + 1
  9.     let swapIndex = root
  10.     if array[swapIndex] < array[child]:
  11.       set swapIndex = child
  12.     if child + 1 ≤ end and array[swapIndex] < array[child + 1]:
  13.       set swapIndex = child + 1
  14.     if swapIndex == root: return
  15.     swap array[root] with array[swapIndex]
  16.     set root = swapIndex

Array Animation

comparing swapping sorted
Press Play or Step Forward to begin.