Heap Sort with Heapify — O(n log n) In-Place Sorting

How Heap Sort Works

Heap Sort leverages the max-heap data structure to sort an array in-place. It consists of two phases: building a max heap from the input data, then repeatedly extracting the maximum element.

Phase 1: Build Max Heap

A max heap is a complete binary tree where each parent is greater than or equal to its children. The array representation stores the tree level by level:

• Parent of node i: floor((i-1)/2)
• Left child of node i: 2*i + 1
• Right child of node i: 2*i + 2

Building the heap bottom-up using heapify takes O(n) time (not O(n log n) as naive analysis suggests).

The Heapify Procedure

heapify(arr, size, i) ensures the subtree rooted at index i satisfies the heap property:

function heapify(arr, size, i):
  largest = i
  left = 2*i + 1
  right = 2*i + 2
  if left < size and arr[left] > arr[largest]:
    largest = left
  if right < size and arr[right] > arr[largest]:
    largest = right
  if largest != i:
    swap(arr[i], arr[largest])
    heapify(arr, size, largest)

Phase 2: Extract Elements

After building the heap, the maximum element is at index 0. We swap it with the last unsorted element, reduce the heap size by 1, and heapify the root:

for i = n-1 down to 1:
  swap(arr[0], arr[i])
  heapify(arr, i, 0)

Complexity Analysis

Metric	Value
Build heap	O(n)
n extractions x heapify	O(n log n)
Total time	O(n log n) — all cases
Space	O(1) — in-place
Stable	No

Why O(n) to Build a Heap?

Intuitively, most nodes are near the bottom of the tree and need to heapify only a small distance. Half the nodes are leaves (no heapify needed), a quarter need at most 1 swap, an eighth need at most 2, and so on. The sum converges to O(n).