Algorithms · Sorting

Heap Sort

The idea

A knockout tournament: after the first rounds, the champion stands on top. Send the champion to the podium (the end of the list), let the next-best fight their way up — one short path of duels, not a whole new tournament — and repeat until everyone is ranked.

The problem

What if the list could always tell you its biggest item instantly? A max-heap does exactly that: arrange the items so every "parent" is bigger than its two "children" — then the biggest is always on top. Heap sort repeats one move: take the top, park it at the end, repair the heap, repeat.

Why it's slow

Heap sort is fast: building the heap is cheap, and each of the n extractions repairs the heap in about log n comparisons — O(n log n) overall, guaranteed, with NO extra memory. Why is it not always the default? Its memory access pattern jumps around (children live far from parents), which real hardware dislikes — so quick sort usually wins the race in practice despite the same big-O.

Pseudocode

  1. first, arrange the list into a max-heap: every parent ≥ its children
    Explain this line

    In the bars: position 0 is the top; children of i sit at 2i+1, 2i+2.

  2. swap the top (the biggest) with the last unsorted item
    Explain this line

    The biggest value teleports straight to its final home.

  3. lock that last position — it is final
    Explain this line

    The locked zone grows from the right, biggest values first.

  4. sift the new top down: compare with children, swap with the bigger one
    Explain this line

    Repairing the heap costs one short walk down, about log n steps.

  5. repeat until every position is locked
    Explain this line

    n removals × log n repair = the O(n log n) total.

Complexity

Best Average Worst Space
O(n log n) O(n log n) O(n log n) O(1)

The safety net: guaranteed n log n, in place. Loses practical races to quick sort because of cache-unfriendly jumps.

Code

python 
def heap_sort(a):
    n = len(a)

    def sift(root, end):
        while (child := 2 * root + 1) <= end:
            if child + 1 <= end and a[child + 1] > a[child]:
                child += 1
            if a[child] > a[root]:
                a[root], a[child] = a[child], a[root]
                root = child
            else:
                return

    for i in range(n // 2 - 1, -1, -1):
        sift(i, n - 1)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end - 1)
    return a
java 
void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) sift(a, i, n - 1);
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;
        sift(a, 0, end - 1);
    }
}

void sift(int[] a, int root, int end) {
    while (2 * root + 1 <= end) {
        int child = 2 * root + 1;
        if (child + 1 <= end && a[child + 1] > a[child]) child++;
        if (a[child] <= a[root]) return;
        int t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}
cpp 
void sift(std::vector<int>& a, int root, int end) {
    while (2 * root + 1 <= end) {
        int child = 2 * root + 1;
        if (child + 1 <= end && a[child + 1] > a[child]) ++child;
        if (a[child] <= a[root]) return;
        std::swap(a[root], a[child]);
        root = child;
    }
}

void heapSort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int i = n / 2 - 1; i >= 0; --i) sift(a, i, n - 1);
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[0], a[end]);
        sift(a, 0, end - 1);
    }
}
javascript 
function heapSort(a) {
  const sift = (root, end) => {
    while (2 * root + 1 <= end) {
      let child = 2 * root + 1;
      if (child + 1 <= end && a[child + 1] > a[child]) child++;
      if (a[child] <= a[root]) return;
      [a[root], a[child]] = [a[child], a[root]];
      root = child;
    }
  };
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) sift(i, n - 1);
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    sift(0, end - 1);
  }
  return a;
}
dart 
void heapSort(List<int> a) {
  void sift(int root, int end) {
    while (2 * root + 1 <= end) {
      var child = 2 * root + 1;
      if (child + 1 <= end && a[child + 1] > a[child]) child++;
      if (a[child] <= a[root]) return;
      final t = a[root];
      a[root] = a[child];
      a[child] = t;
      root = child;
    }
  }

  final n = a.length;
  for (var i = n ~/ 2 - 1; i >= 0; i--) {
    sift(i, n - 1);
  }
  for (var end = n - 1; end > 0; end--) {
    final t = a[0];
    a[0] = a[end];
    a[end] = t;
    sift(0, end - 1);
  }
}

Quick check