Heap Sort Cache Misses — 40% Latency Spike in Trading

Every developer eventually hits a moment where a simple sort isn't good enough — maybe memory is tight, or a worst-case O(n²) from quicksort would be catastrophic in production. Heap sort was designed precisely for those moments. It's used inside priority queues, operating system schedulers, and graph algorithms like Dijkstra's — anywhere you need a guaranteed, predictable sort that never blows up under adversarial input.

The core problem heap sort solves is the tension between speed and memory. Merge sort is also O(n log n), but it needs O(n) extra space to do its work. Quicksort is fast on average but degrades to O(n²) on already-sorted or reverse-sorted data. Heap sort gives you O(n log n) in every case — best, average, and worst — while sorting the array in-place using only O(1) extra space. That's a rare combination.

By the end of this article you'll understand what a max-heap actually is and why it matters, how heapify is the secret engine behind the whole algorithm, how to implement heap sort from scratch in Java with a clear mental model you won't forget, and exactly when to reach for it over quicksort or merge sort in real projects.

How Heap Sort Works — Plain English and Algorithm

Heap sort has two phases: build a max-heap from the array, then repeatedly extract the maximum to produce a sorted array.

A max-heap is a complete binary tree where every parent is larger than its children. The maximum element is always at the root (index 0). We can represent the heap in the same array without extra space: for a node at index i, its left child is at 2i+1 and right child at 2i+2.

Phase 1 — Build a max-heap in O(n): 1. Start from the last non-leaf node (index n//2 - 1) and work backward to index 0. 2. For each node, run 'heapify down': if either child is larger, swap with the larger child and recurse. 3. After processing all nodes, the array satisfies the max-heap property.

Phase 2 — Sort by extracting elements in O(n log n): 4. Swap the root (maximum) with the last element. The maximum is now in its final sorted position. 5. Reduce the heap size by 1 (ignore the last element which is now sorted). 6. Run heapify down on the new root to restore the max-heap property. 7. Repeat steps 4-6 until the heap has one element.

Time complexity: O(n log n) for all cases. Space: O(1) — heap sort is in-place.

Worked Example — Tracing Heap Sort on [4, 10, 3, 5, 1]

Input: [4, 10, 3, 5, 1]

Phase 1 — Build max-heap. Last non-leaf = index 1 (node value 10). Heapify index 1 (value 10): children are index 3 (5) and 4 (1). 10 > both. No swap. Heapify index 0 (value 4): children are index 1 (10) and 2 (3). 10 > 4. Swap 4 and 10. Array: [10, 4, 3, 5, 1]. Now heapify the displaced 4 at index 1: children 5 and 1. 5>4. Swap. Array: [10, 5, 3, 4, 1]. Max-heap built.

Phase 2 — Sort: Iteration 1: Swap root 10 with last element 1. Array: [1, 5, 3, 4, |10]. Heap size=4. Heapify root 1: children 5, 3. 5>1. Swap. Array: [5, 1, 3, 4, |10]. Heapify 1 at index 1: children 4. 4>1. Swap. Array: [5, 4, 3, 1, |10]. Iteration 2: Swap root 5 with 1. Array: [1, 4, 3, |5, 10]. Heap size=3. Heapify root 1: children 4, 3. 4>1. Swap. Array: [4, 1, 3, |5, 10]. Heapify 1 at index 1: no children in heap. Done. Iteration 3: Swap root 4 with 3. Array: [3, 1, |4, 5, 10]. Heap size=2. Heapify root 3: child 1. 3>1. No swap. Iteration 4: Swap root 3 with 1. Array: [1, |3, 4, 5, 10]. Heap size=1. Done.

Final sorted array: [1, 3, 4, 5, 10]

Heap Sort Implementation

Heap sort is implemented in two phases. The build-heap phase constructs a max-heap in-place by calling sift-down (heapify) on every non-leaf node from right to left, taking O(n) total time (not O(n log n) — most nodes are near the bottom and require little sifting). The extraction phase repeatedly swaps the root (maximum element) with the last element of the current heap, reduces the heap size by 1, and sifts the new root down to restore the heap property. Each sift-down is O(log n), and we do n-1 extractions, giving O(n log n) total. Heap sort is not stable and has poor cache performance because of non-sequential memory access during sifting, making quicksort faster in practice despite the same asymptotic complexity.

package io.thecodeforge.sorting;

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;

        // Phase 1: Build max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Phase 2: Extract elements one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // Restore heap property on reduced heap
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int heapSize, int root) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != root) {
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;
            heapify(arr, heapSize, largest);
        }
    }
}

When to Use Heap Sort in Production

Heap sort shines in environments where memory is severely constrained and worst-case performance must be guaranteed. You don't want to allocate a second array (like merge sort) and you can't risk quicksort's O(n²) degenerate case. Real uses: - Embedded systems with limited RAM (e.g., firmware sorting sensor data) - Real-time systems where worst-case latency must be bounded (though watch cache effects) - Priority queue implementations: heap sort's extraction phase is exactly what a priority queue does - Sorting large datasets where memory is too tight for an auxiliary array But for general-purpose sorting on modern hardware, quicksort or introsort (hybrid) almost always beats heap sort. TimSort (used in Python, Java for objects) is also better when input is partially ordered. Use heap sort only when both O(1) space and guaranteed O(n log n) are non-negotiable.

Heap Sort Performance Analysis: Cache Misses and Stability

Let's dig into the performance characteristics that matter in production:

Time Complexity — O(n log n) for all inputs. This is its greatest strength: no pathological cases. But constant factors are high.

Space Complexity — O(1) auxiliary space. The array is sorted in-place using only a few variables. That's a real win when memory is scarce.

Cache Behaviour — This is where heap sort falls down. The heapify operation accesses indices i, 2i+1, 2i+2 which are far apart for large arrays. For an array of 10 million integers (40 MB), parent and child may be in different cache lines — each sift-down causes multiple cache misses. Quicksort, by contrast, partitions contiguous subarrays and enjoys sequential access.

Stability — Heap sort is not stable. The extraction phase swaps elements far apart, so equal elements can change relative order. If stability matters (e.g., sorting by multiple keys), use merge sort or TimSort.

Comparison with Other O(n log n) Sorts — Merge sort uses O(n) space but accesses memory sequentially (good cache). Quicksort uses O(log n) stack space and has excellent cache behaviour. Heap sort's space advantage only matters when memory is so tight you can't allocate a second array.

Frequently Asked Questions