Counting Sort

Sorting O(n + k) O(n + k)

Tallies how many times each value occurs, prefix-sums the counts into final positions, then places each element directly — no comparisons.

Idle

Starting Counting Sort on 8 elements.

Invariantcounts[v] is the number of times v has been seen so far — no comparisons are involved.

1/37

comparisons0moves0probes0max0i0

compareswapshiftselectsorted

counting-sort.c

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
 
    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;
 
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
 
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];
 
    int out[n];
    for (int i = n - 1; i >= 0; i--)
        out[--count[arr[i]]] = arr[i];
 
    for (int i = 0; i < n; i++)
        arr[i] = out[i];
}

How Counting Sort works

Count how many times each value occurs, prefix-sum the counts into final positions, then place each element straight into its slot, scanning from the right for stability.

Best case

O(n + k) always — a couple of linear passes.

Worst case

A huge value range k dominates: counting array of size k must be allocated and swept.

When to use it

Integer keys from a small known range; also the stable pass inside radix sort.