Heap sort with example

Internal and external sorting

Heap sort

Heap sort uses a max-heap: an almost complete binary tree in which every parent is ≥ its children, stored in an array (children of index i at 2i+1 and 2i+2).

Algorithm:

1. Build a max-heap from the array (heapify from the last parent n/2 − 1 down to 0).
2. Swap the root (largest) with the last element of the heap, and reduce the heap size by one. The largest element is now in its final place.
3. Restore the heap property by sifting the new root down.
4. Repeat steps 2–3 until only one element remains.

void sift(int a[], int i, int n) {            /* sift a[i] down in heap of size n */
    int l, g, t;
    while ((l = 2 * i + 1) < n) {
        g = (a[l] > a[i]) ? l : i;
        if (l + 1 < n && a[l + 1] > a[g]) g = l + 1;
        if (g == i) return;
        t = a[i]; a[i] = a[g]; a[g] = t; i = g;
    }
}
void heap_sort(int a[], int n) {
    int i, t;
    for (i = n / 2 - 1; i >= 0; i--) sift(a, i, n);   /* build heap */
    for (i = n - 1; i > 0; i--) {
        t = a[0]; a[0] = a[i]; a[i] = t;              /* move max to end */
        sift(a, 0, i);                                /* repair heap */
    }
}

Example: sort 25, 57, 48, 37, 12, 92, 86, 33

Build the max-heap:

Initial heap: 92, 57, 86, 37, 12, 48, 25, 33

level 0:  92
level 1:  57   86
level 2:  37   12   48   25
level 3:  33

Sorting phase:

Sorted output: 12, 25, 33, 37, 48, 57, 86, 92

Complexity: O(n log n) in best, average and worst case; O(1) extra space; not stable.