Comparison Sorts

Heap Sort

Build a max-heap from the array, then repeatedly extract the max and place it at the end. O(n log n) guaranteed, in-place (O(1) extra space), but not stable. Rarely used in practice but has strong guarantees.

O(n log n)

O(1)

How It Works

Heap sort first rearranges the array into a max-heap — a complete binary tree, stored implicitly in the array, where every parent is at least as large as its children. Building the heap bottom-up by sifting down from the last internal node costs only O(n). Then it repeatedly swaps the root (the maximum) with the last unsorted element, shrinks the heap boundary by one, and sifts the new root down to restore the heap property.

Each of the n extractions costs O(log n) for the sift-down, so the total is O(n log n) guaranteed, with O(1) auxiliary space — the only mainstream comparison sort that is simultaneously worst-case optimal and fully in-place. The trade-offs are instability and poor cache behavior from the strided parent-child jumps, which is why it typically loses to quick sort in practice yet serves as the fallback inside introsort when quick sort's recursion degenerates.

Step-by-Step Visualization

Build max-heap from [4,10,3,5,1]

Max-heap[10,5,3,4,1]

1/3

Code

Java

static void heapSort(int[] arr) {
  int n = arr.length;
  for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
  for (int i = n - 1; i > 0; i--) {
    int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
    heapify(arr, i, 0);
  }
}

static void heapify(int[] arr, int n, int i) {
  int largest = i;
  int l = 2*i+1, r = 2*i+2;
  if (l < n && arr[l] > arr[largest]) largest = l;
  if (r < n && arr[r] > arr[largest]) largest = r;
  if (largest != i) {
    int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
    heapify(arr, n, largest);
  }
}

Tips & Gotchas

1Build a max-heap from the array in O(n)

2Repeatedly extract the max and place at the end

3In-place, not stable, always O(n log n)

Practice Problems

1Sort an Array
2Kth Largest Element in an Array
3Last Stone Weight
4Top K Frequent Elements

About the Comparison Sorts Pattern

Sort by comparing pairs of elements. No comparison sort can do better than O(n log n) in the worst case — this is a proven lower bound. The three main ones differ in stability, space, and constant factors.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

Sort Colors
Kth Largest Element
Merge Intervals
Largest Number
Sort List
Meeting Rooms

Frequently Asked Questions

Why is building a heap O(n) rather than O(n log n)?

Bottom-up heapify sifts each node down at most its height, and node counts shrink geometrically with height: n/2 leaves need no work, n/4 nodes sift one level, n/8 two levels, and so on. The series n * sum(h / 2^(h+1)) converges to O(n), unlike n insertions which each pay O(log n) upward.

If heap sort has ideal guarantees, why is quick sort still preferred?

Constant factors. Heap sort's parent-to-child index jumps ruin cache locality and its inner loop does more comparisons per element moved, so it typically runs two to three times slower than quick sort on real hardware. Introsort gets the best of both: quick sort speed normally, heap sort's O(n log n) bound as a fallback.

For top-k problems, should I sort the whole array with heap sort?

Usually not — maintain a bounded heap of size k instead. Streaming all n elements through a size-k min-heap finds the k largest in O(n log k), which beats the O(n log n) of full sorting whenever k is much smaller than n and also works on data streams.