Heap Sort: Sorting with Binary Heaps

Heap Sort Algorithm

Heap sort uses a binary heap to sort an array. It has O(n log n) worst-case time complexity and sorts in-place with O(1) extra space.

Algorithm Steps

1. Build a max-heap from the input array — O(n)
2. Extract the maximum repeatedly:
   • Swap the root (maximum) with the last unsorted element
   • Reduce the heap size by 1
   • Bubble down the new root to restore the heap property
   • Repeat until the heap is empty

Step-by-Step Example

Input: [4, 1, 7, 3, 9, 2]

Step 1: Build max-heap -> [9, 4, 7, 3, 1, 2]

Step 2: Extract phase
  Swap 9 and 2: [2, 4, 7, 3, 1, | 9]  heapify -> [7, 4, 2, 3, 1, | 9]
  Swap 7 and 1: [1, 4, 2, 3, | 7, 9]  heapify -> [4, 3, 2, 1, | 7, 9]
  Swap 4 and 1: [1, 3, 2, | 4, 7, 9]  heapify -> [3, 1, 2, | 4, 7, 9]
  Swap 3 and 2: [2, 1, | 3, 4, 7, 9]  heapify -> [2, 1, | 3, 4, 7, 9]
  Swap 2 and 1: [1, | 2, 3, 4, 7, 9]

Result: [1, 2, 3, 4, 7, 9]

Complexity Analysis

Metric	Complexity
Build heap	O(n)
n extractions	O(n log n)
Total	O(n log n)
Space	O(1) in-place
Stable?	No

Comparison with Other Sorts

Algorithm	Average	Worst	Space	Stable
Heap sort	O(n log n)	O(n log n)	O(1)	No
Quick sort	O(n log n)	O(n²)	O(log n)	No
Merge sort	O(n log n)	O(n log n)	O(n)	Yes

Heap sort's advantage: Guaranteed O(n log n) worst case with O(1) space. Quick sort can degrade to O(n²) on bad inputs. Merge sort needs O(n) extra space.

Heap sort's disadvantage: Poor cache performance compared to quick sort. Quick sort accesses elements sequentially, while heap sort jumps around the array (parent-child relationships), causing cache misses.

When to Use Heap Sort

• When worst-case O(n log n) is required (real-time systems)
• When O(1) extra space is required
• When stability is not needed
• As a fallback: many standard library sorts use introsort (quick sort that falls back to heap sort when recursion depth gets too deep)