Heap sort

Heap sort sorts an array in two phases: build a max-heap from the array, then repeatedly extract the maximum and place it at the end. Runs in $O(n\log n)$ in all cases — best, average, and worst — and sorts in place (no auxiliary array needed).

The two phases:

1. Heapify: rearrange the array into a max-heap. The largest element ends up at index 0.
2. Extract repeatedly: swap the root with the last element of the heap, then re-heapify the (now smaller) heap. The extracted maximum is now at the end. Repeat.

After all extractions, the array is sorted in ascending order.

Phase 1: build the heap

A max-heap has every parent ≥ its children. To turn an arbitrary array into a max-heap:

1. Find the index of the last non-leaf node: $\lfloor n/2\rfloor -1$.
2. Starting from this index and moving back to the root, sift down each node: compare it with its children and swap with the larger child if the heap property is violated. Continue sifting until that subtree satisfies the heap property.

After visiting every non-leaf node bottom-up, the entire array satisfies the heap property — arr[0] is the maximum.

The leaf nodes (indices $\lfloor n/2\rfloor$ to $n-1$) trivially satisfy the heap property by themselves, so we skip them.

Cost of build: $O(n)$ — surprisingly, not $O(n\log n)$. The deeper analysis shows the work is bounded by the sum of heights at each level, which converges to a linear total.

Phase 2: extract

After building the heap, the array conceptually has two regions: the heap (front) and the sorted suffix (back). Initially the entire array is heap and the sorted region is empty.

Repeat:

1. Swap arr[0] (the heap’s max) with arr[heapEnd] (the last position in the heap region). The max is now at the end of the array.
2. Decrement the heap size by 1 (the last position is now the start of the sorted region).
3. Re-heapify the new root (sift down from index 0). The new max bubbles to position 0.

After $n-1$ such extractions, the heap region shrinks to one element and the sorted region holds everything else in ascending order.

Worked example

For arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 4] ($n=10$):

Build the heap. Last non-leaf is at index $10/2-1=4$. Sift down from index 4 down to index 0. Each sift moves an element to its correct position in the heap.

Extract. Swap root with end, shrink heap, sift down. Repeat.

After all extractions:

Big O

• Build: $O(n)$.
• Each extract: $O(\log n)$.
• Total extract phase: $O(n\log n)$.
• Overall: $O(n\log n)$.

This is the same asymptotic complexity as Merge sort and average-case Quick sort.

Properties

• In place: $O(1)$ extra space (besides the array itself).
• Not stable: equal elements can change relative order during sift operations.
• Worst case = best case = average case = O(n log n): no input pattern degrades it. (Compare with quicksort’s $O(n^2)$ worst case.)

When to use it

Heap sort is useful when:

• You need guaranteed $O(n\log n)$ worst-case performance (quicksort can degrade).
• Memory is tight ($O(1)$ extra space, vs. merge sort’s $O(n)$).
• Stability isn’t required.

In practice, quicksort tends to outperform heap sort by a constant factor on real workloads (better cache behavior, fewer swaps), so heap sort is often a “fallback” choice rather than the default.

The same structural ideas underpin heap-based priority queues — building a heap, sifting up on insert, sifting down on extract — but the sorting application uses these inside an in-place transformation rather than maintaining a queue over time.