Counting Sort

Every sorting algorithm you’ve seen so far — quicksort, merge sort, heap sort — relies on comparing elements to determine order. A fundamental result in computer science proves that any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case. This is a hard mathematical floor, not a limitation of current algorithms.

Counting sort blasts through that floor by refusing to compare elements at all. Instead, it counts them.

The Requirement

Counting sort works under a specific constraint: the elements are integers in a known range [0, k]. When this condition holds, counting sort achieves O(n + k) time — which is O(n) when k = O(n).

This restriction is the trade-off. You give up generality; you gain linear time.

The Algorithm

The algorithm proceeds in three phases:

Phase 1: Count Occurrences

Create a count array of size k + 1. Scan the input and tally how many times each value appears.

Phase 2: Compute Prefix Sums

Transform the count array so that count[i] contains the number of elements less than or equal to i. This tells you the final position of the last occurrence of each value.

Phase 3: Place Elements

Iterate through the input array backwards (this is critical for stability). For each element with value v, place it at position count[v] - 1 in the output array, then decrement count[v].

Java 25 Implementation

int[] countingSort(int[] arr, int k) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[k + 1];   // count[i] = occurrences of value i

    // Phase 1: Count occurrences
    for (int val : arr) {
        count[val]++;
    }

    // Phase 2: Prefix sums — count[i] now holds position of last element with value i
    for (int i = 1; i <= k; i++) {
        count[i] += count[i - 1];
    }

    // Phase 3: Build output (iterate backwards for stability)
    for (int i = n - 1; i >= 0; i--) {
        int val = arr[i];
        output[count[val] - 1] = val;
        count[val]--;
    }

    return output;
}

Visual Walkthrough

Input: [4, 2, 2, 8, 3, 3, 1], k = 8

Phase 1 — Count:

Index:  0  1  2  3  4  5  6  7  8
Count:  0  1  2  2  1  0  0  0  1

Value 1 appears once, value 2 appears twice, value 3 appears twice, value 4 appears once, value 8 appears once.

Phase 2 — Prefix Sums:

Index:  0  1  2  3  4  5  6  7  8
Count:  0  1  3  5  6  6  6  6  7

Now count[3] = 5 means there are 5 elements with value ≤ 3. The last element with value 3 goes at index 4 (position 5 - 1).

Phase 3 — Place (backwards):

i=6: arr[6]=1, count[1]=1 → output[0]=1, count[1]=0
i=5: arr[5]=3, count[3]=5 → output[4]=3, count[3]=4
i=4: arr[4]=3, count[3]=4 → output[3]=3, count[3]=3
i=3: arr[3]=8, count[8]=7 → output[6]=8, count[8]=6
i=2: arr[2]=2, count[2]=3 → output[2]=2, count[2]=2
i=1: arr[1]=2, count[2]=2 → output[1]=2, count[2]=1
i=0: arr[0]=4, count[4]=6 → output[5]=4, count[4]=5

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

Why Iterate Backwards?

The backward iteration in Phase 3 ensures stability. When two elements have the same value, the one appearing later in the input array gets placed at a higher index in the output array. Since we traverse backwards, the first occurrence (lower index in input) ends up at its correct lower position.

If you iterate forwards, equal elements appear in reverse order — making the sort unstable. This matters because radix sort depends on counting sort being stable.

Analysis

Time Complexity: O(n + k)

• Phase 1 (counting): O(n) — one pass through the input.
• Phase 2 (prefix sums): O(k) — one pass through the count array.
• Phase 3 (placement): O(n) — one pass through the input.
• Total: O(n + k)

When k = O(n), this becomes O(n) — linear time sorting.

Space Complexity: O(n + k)

• Count array: O(k + 1) = O(k)
• Output array: O(n)
• Total: O(n + k)

Counting sort is not in-place. It requires both the count array and the output array.

Stability: Yes

As explained above, the backward iteration preserves the relative order of equal elements. This property is essential when counting sort serves as a subroutine in radix sort.

Not Comparison-Based

Counting sort never compares two elements against each other. It uses element values as array indices, which is an entirely different computation model. This is why it doesn’t violate the Ω(n log n) lower bound — that bound applies exclusively to comparison-based algorithms.

The lower bound proof uses a decision tree argument: any comparison sort can be modeled as a binary tree of comparisons, and the tree needs at least n! leaves (one per permutation), so its height must be at least log₂(n!) = Ω(n log n). Counting sort bypasses this tree entirely.

Why Not Always Use Counting Sort?

If counting sort is O(n), why bother with O(n log n) algorithms? Three practical constraints limit its applicability:

1. Range Must Be Small Relative to n

If you sort 10 elements in the range [0, 1,000,000], you allocate a count array of size 1,000,001 — a massive waste. The O(n + k) time becomes O(k) = O(1,000,000), far worse than O(n log n) = O(10 × 3.3) ≈ 33 operations.

Rule of thumb: counting sort pays off when k ≤ n or at least k = O(n).

2. Elements Must Be Integers (or Mappable to Integers)

You can’t count sort floating-point numbers or strings directly. The elements must serve as array indices. Characters work (ASCII range 0–127), ages work (0–150), grades work (0–100), but arbitrary data types don’t.

3. Extra Memory Required

Counting sort needs O(n + k) space. For memory-constrained environments, this overhead is prohibitive.

Counting Sort as a Subroutine

Counting sort’s primary role in practice is as the stable sorting subroutine inside radix sort. Radix sort processes one digit at a time, using counting sort to sort by each digit position. Since each digit has a small range (0–9 for base 10, 0–255 for byte-level), counting sort runs in O(n + k) = O(n + 10) = O(n) per digit.

The stability guarantee ensures that elements sorted by digit position d remain in order when sorted by digit position d + 1.

Here’s counting sort parameterized for use in radix sort — sorting by a specific digit:

void countingSortByDigit(int[] arr, int n, int exp) {
    int[] output = new int[n];
    int[] count = new int[10];  // Base 10 digits: 0–9

    // Count occurrences of each digit at position exp
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // Prefix sums
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build output (backwards for stability)
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    System.arraycopy(output, 0, arr, 0, n);
}

Variation: Handling Negative Numbers

Standard counting sort handles only non-negative integers. To support negative numbers, offset the range:

int[] countingSortWithNegatives(int[] arr) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int val : arr) {
        min = Math.min(min, val);
        max = Math.max(max, val);
    }

    int range = max - min + 1;
    int[] count = new int[range];
    int[] output = new int[arr.length];

    for (int val : arr) {
        count[val - min]++;     // Shift by min to handle negatives
    }

    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    for (int i = arr.length - 1; i >= 0; i--) {
        int shifted = arr[i] - min;
        output[count[shifted] - 1] = arr[i];
        count[shifted]--;
    }

    return output;
}

The offset val - min maps any integer range into [0, max - min], making it usable as an array index.

Practical Use Cases

Counting sort works well for:

• Sorting characters: ASCII range is 128, Unicode basic range is 65,536 — both tractable.
• Sorting ages: range [0, 150] — trivially small.
• Sorting exam scores: range [0, 100] — perfect fit.
• Sorting RGB color channels: range [0, 255] per channel.
• Frequency analysis: the count array itself is often the desired output (histogram of values).
• Sorting database records by integer keys with known bounds.

Interviewer Tips

• State the constraint upfront: when an interviewer asks about sorting, clarify the input domain. If elements are integers in a bounded range, counting sort gives you O(n). Demonstrate that you know when to reach beyond comparison sorts.
• Explain why it’s not cheating: interviewers want to hear that the Ω(n log n) bound applies to comparison sorts, and counting sort uses a different computation model (indexing, not comparing).
• Stability is the key detail: many candidates implement counting sort but forget the backward iteration. If your counting sort isn’t stable, it breaks radix sort. Emphasize this in your explanation.
• Know the space trade-off: “Why not always use counting sort?” is a common follow-up. Answer with the k vs. n relationship and the integer-only constraint.
• Connect to radix sort: show that you understand counting sort’s role as a building block. This demonstrates systems-level thinking beyond isolated algorithms.