Heap sort and counting sort

Introduction

Two more sorts complete the picture: one that is O(n log n) and needs no extra array, and one that beats O(n log n) by not comparing items at all.

With merge sort and quick sort done, two questions remain: can a sort be fast with no extra array, and can any sort beat O(n log n)? Heap sort answers the first, and counting sort the second.

How it works

Counting sort

#include <stdio.h>
#define MAX 5

int main(void) {
    int a[] = {3, 1, 4, 1, 5, 2, 3, 0};
    int n = 8;
    int count[MAX + 1] = {0};
    for (int i = 0; i < n; i++) count[a[i]]++;
    int k = 0;
    for (int v = 0; v <= MAX; v++)
        for (int c = 0; c < count[v]; c++) a[k++] = v;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

When the values are small whole numbers, say marks from 0 to 100, you can count how many times each value appears, then write the values out in order. No item is ever compared with another. With n items and values from 0 to k, it takes O(n + k) time and O(k) extra memory.

Counting sort only works for keys that can index an array: small integers, or things mapped to them (grades A to F, ages, days of the month).

The O(n log n) limit

Any sort that works only by comparing pairs of items needs about n log₂ n comparisons in the worst case. (There are n! possible orders, and each comparison can at best halve the possibilities.) So merge sort, heap sort and average quick sort are as fast as a comparison sort can be. Counting sort escapes the limit because it does not compare.

Syntax

for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);   // build the heap
swap(&a[0], &a[end]);                                      // the largest to the end
sift_down(a, end, 0);                                      // repair the smaller heap

Example

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

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

void heap_sort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);   // build a max-heap
    for (int end = n - 1; end > 0; end--) {
        swap(&a[0], &a[end]);   // the largest goes to the end
        sift_down(a, end, 0);   // the heap is now a[0 .. end-1]
    }
}

int main(void) {
    int a[] = {4, 10, 3, 5, 1};
    heap_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Heap sort uses the max-heap from the Data Structures course, inside the array being sorted:

1. Build a max-heap from the array (sift down from n/2 - 1 to 0): O(n).
2. The largest item is at a[0]. Swap it with the last item of the heap, shrink the heap by one, and sift the new root down: O(log n). The sorted part grows from the right end.
3. Repeat until the heap has one item.

It is always O(n log n) and in place, but not stable, and in practice a little slower than quick sort.

Line by line

1. sift_down compares the item at i with its children at 2 * i + 1 and 2 * i + 2.
2. Tests like l < n stop it from reading past the end of the heap.
3. If the item is already the largest of the three, the function returns. Otherwise it swaps with the larger child and carries on from there.
4. In heap_sort, the first loop builds a max-heap, starting at the last parent, n / 2 - 1.
5. The second loop swaps the root to position end, where it is final, and sifts the new root down within the smaller heap.
6. main sorts five numbers and prints them.

Expected result

1 3 4 5 10 

In the real world

The Linux kernel's general-purpose sort function uses heap sort, because it has no bad case and needs no extra memory. Counting sort is the building block of radix sort, which orders fixed-length keys such as dates or ID numbers.

Common mistakes

• Passing n instead of end to sift_down in the second loop, which pulls the sorted items back into the heap.
• Using counting sort when values are huge or negative, without mapping them to small indexes first.
• Starting the build loop at index 0 and working up, which does not produce a heap.

Best practices

• Reuse a tested sift_down for both the build and the sort.
• Check the range of the values before choosing counting sort.
• Use heap sort when memory is tight and the worst case matters.

Summary

Heap sort builds a max-heap in the array and repeatedly moves the root to the end, in O(n log n) with no extra array. Counting sort avoids comparisons altogether, in O(n + k), when keys are small whole numbers.

Mark lesson complete