Counting sort

Counting sort is a non-comparison sort that works on integer keys drawn from a small range. It counts how many times each value appears, then uses those counts to compute each element’s final position. Linear time — $O(n+k)$ where $k$ is the range of values — making it dramatically faster than comparison sorts when the range is small.

Counting sort doesn’t compare elements to each other. It exploits the structure of integer keys directly. This is the same trick that lets Radix sort (which uses counting sort internally) beat the $\Omega (n\log n)$ lower bound that applies to comparison-based sorts.

Algorithm

For an input array arr[0..n-1] with values in $[0,k)$:

1. Count: for each value $v$ in the input, increment count[v].
2. Cumulative sum: replace each count[v] with the sum of itself and all previous counts. Now count[v] tells you how many elements have value ≤ $v$ — i.e., the position right after the last $v$ in sorted order.
3. Place: walk the input backward. For each element with value $v$, decrement count[v] and place the element at output[count[v]]. The backward iteration preserves stability (equal elements keep their relative order).

void countingSort(int arr[], int n, int k) {
    // C99 VLAs — fine for small k. For large k (say k = 10^6+) these
    // sit on the stack and will overflow. Use malloc/calloc instead
    // when k can be large; precisely the case where counting sort is
    // already wasteful, but the code shouldn't crash.
    int count[k];
    int output[n];
 
    // Step 1: count occurrences
    for (int i = 0; i < k; i++) count[i] = 0;
    for (int i = 0; i < n; i++) count[arr[i]]++;
    
    // Step 2: cumulative count
    for (int i = 1; i < k; i++) count[i] += count[i - 1];
    
    // Step 3: place elements (backward for stability)
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    
    // Copy back to arr
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

Worked example

arr = [4, 2, 2, 8, 3, 3, 1], range $k=9$ (values 0..8).

Count:

count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
       (one 1, two 2s, two 3s, one 4, one 8)

Cumulative count:

count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
       (0 elements ≤ 0, 1 element ≤ 1, 3 elements ≤ 2, ...)

Place (walking arr backward):

• arr[6] = 1: count[1] = 1, place at output[0]. count[1] becomes 0.
• arr[5] = 3: count[3] = 5, place at output[4]. count[3] becomes 4.
• arr[4] = 3: count[3] = 4, place at output[3]. count[3] becomes 3.
• arr[3] = 8: count[8] = 7, place at output[6]. count[8] becomes 6.
• arr[2] = 2: count[2] = 3, place at output[2]. count[2] becomes 2.
• arr[1] = 2: count[2] = 2, place at output[1]. count[2] becomes 1.
• arr[0] = 4: count[4] = 6, place at output[5]. count[4] becomes 5.

Output: [1, 2, 2, 3, 3, 4, 8] ✓

Big O

• Time: $O(n+k)$ where $n$ is the number of elements and $k$ is the value range.
• Space: $O(n+k)$ — the count and output arrays.

When $k$ is comparable to $n$ (or smaller), counting sort runs in linear time.

When $k$ is much larger than $n$ (e.g., sorting 10 integers in the range $\mathrm{0..1}{0}^9$), counting sort is wasteful — you’d allocate a $10^9$-element count array to sort 10 things. In that case use a comparison sort.

Stability

Counting sort is stable when the placement step iterates backward through the input. Iterating forward instead would reverse the relative order of equal elements.

Stability matters when counting sort is used as a building block for Radix sort — radix sort processes one digit at a time, and each pass must preserve the relative order from the previous pass.

When to use

Direct uses:

• Small range integer keys: ages, grades, RGB color components.
• Histogram-style data: when counting is the goal anyway.

Indirect uses:

• As a subroutine in Radix sort: counting sort handles each digit position.
• As a subroutine in graph algorithms: e.g., counting sort over edge weights.

For the comparison-based linear-time sort that handles arbitrary value ranges (with multiple passes), see Radix sort. For the related range-based linear sort, see Bucket sort.