Heap Sort Visualizer

How it works

1. Phase 1 — build a max-heap in place with the bottom-up method: sift down every internal node from ⌊n/2⌋ − 1 to 0. O(n).
2. Phase 2: for end from n − 1 down to 1, swap a[0] (the current maximum) with a[end]. That key is now in its final position.
3. The heap is now a[0 … end − 1]; sift the new root down within that range to restore the heap property.
4. When end reaches 0 the array is sorted in ascending order — the sorted tail has grown to cover everything.

The idea: a shrinking heap and a growing sorted tail

Heap sort is selection sort with a better data structure. Selection sort finds the maximum by scanning every remaining element — O(n) per pick. Heap sort keeps the remaining elements in a max-heap, so the maximum is always at a[0] and restoring the heap after removing it costs only O(log n).

Throughout phase 2 the array has two regions: a max-heap at the front and a sorted run of the largest keys at the back. Each swap moves the current maximum from the root to the slot just before the sorted run, so the run grows by one and the heap shrinks by one — no second array needed.

Worked example: 29, 7, 45, 13, 61, 2, 38, 20

This input is preloaded in the visualizer above.

Phase 1. n = 8, so sift-down runs on indices 3, 2, 1, 0: 13 sinks below 20, 45 already beats its children, 7 sinks below 61, and 29 sinks below 61. Three swaps produce the max-heap [61, 29, 45, 20, 7, 2, 38, 13].

Phase 2, shown as heap | sorted tail after each round:

• swap 61 ↔ 13, sift 13 down → [45, 29, 38, 20, 7, 2, 13] | [61]
• swap 45 ↔ 13, sift down → [38, 29, 13, 20, 7, 2] | [45, 61]
• swap 38 ↔ 2, sift down → [29, 20, 13, 2, 7] | [38, 45, 61]
• swap 29 ↔ 7, sift down → [20, 7, 13, 2] | [29, 38, 45, 61]
• swap 20 ↔ 2, sift down → [13, 7, 2] | [20, 29, 38, 45, 61]
• swap 13 ↔ 2, sift down → [7, 2] | [13, 20, 29, 38, 45, 61]
• swap 7 ↔ 2 → [2] | [7, 13, 20, 29, 38, 45, 61]

Result: 2, 7, 13, 20, 29, 38, 45, 61. Press play to watch each swap travel along the tree edges while the locked, sorted tail fills the array from the right.

Heap sort vs quick sort vs merge sort

• Worst case: heap sort and merge sort are O(n log n) on every input; quick sort degrades to O(n²) on bad pivots.
• Extra memory: heap sort needs O(1), quick sort O(log n) for its recursion, array merge sort O(n).
• Stability: only merge sort is stable.
• Speed in practice: quick sort is usually fastest, then merge sort. Heap sort trails because sift-down jumps from index i to 2i + 1, scattering memory accesses and defeating the CPU cache on large arrays.

That combination — a guaranteed O(n log n) with no extra memory, but a slower constant factor — is exactly why introsort, the algorithm behind most C++ std::sort implementations, starts with quick sort and switches to heap sort only when the recursion gets suspiciously deep.

Why heap sort is not stable

A sort is stable if equal keys keep their original order. Heap sort breaks this because the long-distance swap of the root with a[end] can carry one equal key past another. Take [5a, 5b, 3], which is already a max-heap. The first round swaps the root 5a to the end, leaving [3, 5b] | [5a]; sifting gives [5b, 3], and the next round puts 5b in slot 1. The output is 3, 5b, 5a — the two 5s have changed places. If you need stability, use merge sort, or sort (key, original_index) pairs.

Variations: descending order and partial sorting

Build a min-heap instead and the same loop moves the smallest key to the end each round, so the array comes out in descending order — switch the visualizer to Min to see it. If you only need the k largest keys, stop phase 2 after k rounds: the cost is O(n + k log n), which beats a full sort when k is small. Heaps are the standard tool for such top-k problems; C++'s std::partial_sort is heap-based too.

Common mistakes

• Sifting down with the full length n instead of the current heap size end — the sift then drags already-sorted keys back into the heap.
• Using a min-heap and expecting ascending order in place. In-place heap sort with a min-heap yields descending order.
• Running the loop down to zero. The last remaining key is already in place, so the loop stops at end = 1.
• Skipping phase 1. Swapping out the root of an array that is not yet a heap does not move the maximum.

Time and space complexity

Heap Sort in Python

def heap_sort(a):
    # sorts ascending, in place
    build_heap(a)  # O(n)
    n = len(a)
    for end in range(n - 1, 0, -1):
        # the max moves to its final slot
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)  # heap = a[0:end]


def build_heap(a):
    n = len(a)
    # a[n // 2:] are leaves, already heaps
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)


def sift_down(a, i, n):
    # sink a[i] inside the heap a[0:n]
    while 2 * i + 1 < n:
        l, r = 2 * i + 1, 2 * i + 2
        largest = l
        if r < n and a[r] > a[l]:
            largest = r
        if a[i] >= a[largest]:  # in order
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Binary Heap VisualizerBinary heap visualizer: watch sift-up and sift-down in the tree and array side by side. Learn min-heap vs max-heap and O(log n) insert and extract, with code.
• Build Heap (Heapify) — Why It's O(n)Build-heap (heapify) turns an array into a binary heap in O(n) by sifting down from the last parent up to the root. Watch it and see why it beats n inserts.
• Priority Queue VisualizerPriority queue visualizer: a binary heap always serves the top-priority item first. Watch insert, peek and extract in O(log n) and see how Dijkstra uses it.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.
• Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
• Quick Sort VisualizerQuick sort picks a pivot, moves smaller values left and larger ones right, then recurses: O(n log n) on average. Watch Lomuto and Hoare partitioning animated.