When to Use Counting Sort

Direct Answer

Use counting sort when the values are integer keys drawn from a small, known range. It counts how often each key appears, then rebuilds the sorted result in O(n + k) time, where k is the size of the value range. It can beat comparison sorts when k is reasonably close to n, but its O(k) counting storage makes it a poor choice for a huge or sparse range.

Deep Dive & Architecture

Take the input [4, 2, 2, 1, 3]. Its values lie between 1 and 4, so a count array with four useful positions is enough.

1. Count: the frequencies for 1 through 4 become [1, 2, 1, 1].
2. Order: visit the counters from the smallest value to the largest.
3. Emit: write one 1, two 2s, one 3, and one 4, giving [1, 2, 2, 3, 4].

No pair of input values was compared. That is why the comparison-sort lower bound does not apply: counting sort uses extra knowledge about the keys. Its cost is n visits to count plus k visits to scan the range.

For records, cumulative counts answer a stronger question: what is the final ending position of each key? Placing records from right to left then preserves the order of records with the same key, which makes the sort stable.

Code Example

static int[] countingSort(int[] values, int min, int max) {
    int[] counts = new int[max - min + 1];
    for (int value : values) {
        counts[value - min]++;       // offset also supports negatives
    }

    int[] sorted = new int[values.length];
    int out = 0;
    for (int i = 0; i < counts.length; i++) {
        while (counts[i]-- > 0) {
            sorted[out++] = i + min;
        }
    }
    return sorted;
}

// [4, 2, 2, 1, 3] -> [1, 2, 2, 3, 4]

This compact version sorts integer values. Sorting records stably needs cumulative counts and a separate output array.

Common Mistakes & Pitfalls

Looking only at the number of items and forgetting that memory and running time also depend on the distance between the smallest and largest key.