Counting sort

Sort small integers without comparing them: count how many of each value there are, then write them out in order.

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

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

The idea

When values come from a small range 0..k, use each value as an index into a counter array. Reading the counters from left to right gives the sorted order.

Code

C++PythonC#

vector<int> countingSort(const vector<int>& a, int maxVal) {
    vector<int> count(maxVal + 1, 0);
    for (int x : a) count[x]++;
    vector<int> result(a.size());
    int k = 0;
    for (int v = 0; v <= maxVal; v++)
        while (count[v]-- > 0) result[k++] = v;
    return result;
}

def counting_sort(a: list[int], max_value: int) -> list[int]:
    count = [0] * (max_value + 1)
    for x in a: count[x] += 1
    result = []
    for v in range(max_value + 1):
        result.extend([v] * count[v])
    return result

public static int[] CountingSort(int[] a, int max) {
    var count = new int[max + 1];
    foreach (int x in a) count[x]++;
    var result = new int[a.Length];
    int k = 0;
    for (int v = 0; v <= max; v++)
        while (count[v]-- > 0) result[k++] = v;
    return result;
}

Tips

Comparison sorts cannot beat O(n log n). Counting sort does, because it never compares.
Only practical when k is not much larger than n. It is the building block of radix sort.

In the .NET library

new int[size] is zero-initialised in C#, so the counters start at 0 with no extra loop.