Heap sort

Turn the array into a max-heap, then repeatedly move the largest value to the end.

Time O(n log n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

In a max-heap the largest value sits at index 0. Swap it with the last unsorted slot, shrink the heap by one, and sift the new root down to repair the heap.

Code

C++PythonC#

void siftDown(vector<int>& a, int i, int n) {
    while (true) {
        int big = i, l = 2 * i + 1, r = l + 1;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(a[i], a[big]);
        i = big;
    }
}

void heapSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        swap(a[0], a[end]);
        siftDown(a, 0, end);
    }
}

def heap_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)
    # sorted in place

def sift_down(a: list[int], i: int, n: int) -> None:
    while True:
        big, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and a[l] > a[big]: big = l
        if r < n and a[r] > a[big]: big = r
        if big == i: return
        a[i], a[big] = a[big], a[i]
        i = big

public static void HeapSort(int[] a) {
    int n = a.Length;
    for (int i = n / 2 - 1; i >= 0; i--) SiftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        (a[0], a[end]) = (a[end], a[0]);
        SiftDown(a, 0, end);
    }
}

static void SiftDown(int[] a, int i, int n) {
    while (true) {
        int big = i, l = 2 * i + 1, r = l + 1;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        (a[i], a[big]) = (a[big], a[i]);
        i = big;
    }
}

Tips

Building the heap bottom-up from the last parent takes O(n), not O(n log n).
In place and O(n log n) in the worst case, but not stable.

In the .NET library

Array.Sort switches to heap sort when quick sort recursion gets too deep. That fallback is what guarantees O(n log n).