Heap Sort and Sorting Without Comparisons

Merge sort is O(n log n) but needs O(n) memory. Quick sort is in place but has an O(n²) worst case. Heap sort is the algorithm that gives you both guarantees at once, and it is still not the one anyone uses by default.

Heap sort

A max-heap is an array read as a binary tree, where every parent is at least as large as its children. Node i has children at 2i+1 and 2i+2. So the largest value is always at index 0.

That gives an algorithm: build a heap, swap the root to the end (where it belongs), shrink the heap by one, and restore the heap property. Repeat.

The build phase runs bottom-up from the last internal node. That ordering matters: building this way is O(n), whereas inserting n elements one at a time would be O(n log n).

So why is it not the default? Cache behavior. Sift-down jumps between indices i, 2i+1 and 2i+2, which on a large array means jumping across memory and missing the cache constantly. Quick sort scans linearly and is often two or three times faster in wall-clock terms despite the worse asymptotic worst case. Heap sort survives mostly as introsort's safety net.

Getting under n log n

The lower bound from the introduction applies only to algorithms that learn about the data by comparing elements. If you use the values themselves as array indices, the argument does not apply at all.

Counting sort

Count how many of each value there are, then write them back out in order. No comparison ever happens.

It runs in O(n + k), where k is the size of the value range. That is linear when k is comparable to n, and catastrophic when it is not: sorting a handful of 32-bit integers this way would allocate four billion buckets. The precondition is not a footnote, it is the whole trade.

Counting sort is stable as long as you emit each bucket's values in the order they arrived, which is what makes it usable as the inner loop of radix sort.

Radix sort

Radix sort applies a stable counting sort to one digit at a time, least significant first. After processing every digit the array is fully sorted, in O(d × (n + k)) for d digits.

The stability requirement is load-bearing rather than a nicety, since each pass must preserve the ordering established by the previous, less significant, digits. Swap in an unstable sort for the per-digit pass and radix sort simply produces the wrong answer.

The last row is why comparison sorts remain the default. Counting and radix sort need keys that map onto small integers; a comparison sort only needs to be told which of two things comes first, which works for strings, records, and anything else you can define an order on.

In code

function heapSort(a) {
  const n = a.length;

  // Bottom-up build: leaves are already valid heaps, so start at the last
  // internal node. This is O(n), unlike n separate insertions.
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n - 1);

  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];   // largest value goes to its final slot
    siftDown(a, 0, end - 1);
  }
  return a;
}

function siftDown(a, root, end) {
  while (2 * root + 1 <= end) {
    const left = 2 * root + 1;
    const right = left + 1;
    let largest = root;

    if (a[left] > a[largest]) largest = left;
    if (right <= end && a[right] > a[largest]) largest = right;
    if (largest === root) return;

    [a[root], a[largest]] = [a[largest], a[root]];
    root = largest;
  }
}

// Counting sort: one bucket per distinct value, so k must be small.
function countingSort(a, k) {
  const counts = new Array(k).fill(0);
  for (const v of a) counts[v]++;

  let write = 0;
  for (let value = 0; value < k; value++) {
    for (let c = 0; c < counts[value]; c++) a[write++] = value;
  }
  return a;
}

Check yourself

As flowcharts

The same algorithms, drawn as flowcharts, where the dashed copper arrows are loops back to an earlier step, and clicking any box with a dot shows why that step is there.

Heap sort as a flowchart.

Counting sort as a flowchart.