Counting Sort — Non-Comparison Based Sorting

What does it solve?

Sorts integers in linear time by counting how many times each value appears. No comparisons between elements at all. Works best when the range of values (K) is not significantly larger than the number of elements (N).

Key insight: if you know an element's count and the count of everything smaller, you know its exact final position. Prefix sums of the count array give you that.

Three Phases

// Phase 1: Count occurrences
count[val - min]++

// Phase 2: Prefix sum (cumulative)
count[i] += count[i - 1]

// Phase 3: Place elements (right to left)
output[--count[val - min]] = val

Interactive Visualization

Current Element

Counting

Prefix Sum

Placed / Done

Array:

Input Array

Count Array

Press Play or Next to begin

Output Array

—

Step 0 of 0

Phase

Init

Range (K)

Counted

Placed

Ready. Press Play or Next to start the Counting Sort animation.

✓ Sorted

Speed

Step-by-Step Walkthrough

Phase	Description
1. Count	Scan input left to right. For each element, increment count[val - min].
2. Prefix Sum	Accumulate: count[i] += count[i-1]. Now count[i] = position after last occurrence of value i+min.
3. Place	Scan input right to left. Place each element at output[--count[val-min]]. This preserves stability.
4. Done	Output array is the final sorted result.

C++ — Counting Sort (Stable)

vector<int> countingSort(vector<int>& arr) {
    int n = arr.size();
    int mn = *min_element(arr.begin(), arr.end());
    int mx = *max_element(arr.begin(), arr.end());
    int range = mx - mn + 1;

    vector<int> count(range, 0), output(n);

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

    // Phase 2: Prefix sum
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // Phase 3: Place elements (right to left for stability)
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - mn] - 1] = arr[i];
        count[arr[i] - mn]--;
    }

    return output;
}

Complexity

Time

O(N + K)

N elements, K is the range of values (max - min + 1). Always linear.

Space

O(N + K)

Count array of size K, plus output array of size N.

Stable?

Yes

Right-to-left placement preserves relative order of equal elements.

In-Place?

Requires extra arrays for count and output.

📝 Notes

▼