Counting Sort Algorithm in DSA C++

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by counting how many balls of each color you have, then lining them up color by color based on those counts.

Input array: 4 -> 2 -> 2 -> 8 -> 3 -> 3 -> 1 -> null
Count array: [0,0,0,0,0,0,0,0,0]
Output array: [ , , , , , , , ]

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input: 4 -> 2 -> 2 -> 8 -> 3 -> 3 -> 1 -> null
Max value: 8

Why: We need to know the range of numbers to create the count array

Step 2: Initialize count array with zeros for each number from 0 to max

Count array: [0,0,0,0,0,0,0,0,0]

Why: Prepare to count occurrences of each number

Step 3: Count each number's frequency in the input array

Count array after counting: [0,1,2,2,1,0,0,0,1]

Why: We know how many times each number appears

Step 4: Modify count array to store cumulative counts

Count array cumulative: [0,1,3,5,6,6,6,6,7]

Why: Cumulative counts tell the position of each number in output

Step 5: Place each element from input into output array using count array

Output array after placing elements: [1,2,2,3,3,4,8]

Why: Build the sorted array by placing elements at correct positions

Result:

Sorted array: 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 8 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return; // handle empty array

    int max_val = arr[0];
    for (int num : arr) {
        if (num > max_val) max_val = num; // find max value
    }

    vector<int> count(max_val + 1, 0); // count array
    for (int num : arr) {
        count[num]++; // count frequency
    }

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

    vector<int> output(arr.size());
    for (int i = (int)arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i]; // place element
        count[arr[i]]--; // decrease count
    }

    for (int i = 0; i < (int)arr.size(); i++) {
        arr[i] = output[i]; // copy back to original
    }
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
        cout << num << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

for (int num : arr) { if (num > max_val) max_val = num; }

find the maximum value to size count array

for (int num : arr) { count[num]++; }

count frequency of each number

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

compute cumulative counts for positions

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

place elements in output array in sorted order

for (int i = 0; i < (int)arr.size(); i++) { arr[i] = output[i]; }

copy sorted output back to original array

Output

1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 8 -> null

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and process count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Unlike comparison sorts (O(n log n)), counting sort is faster when range k is not much larger than n

Edge Cases

empty array

function returns immediately without error

DSA C++

if (arr.empty()) return;

array with one element

array remains unchanged as it is already sorted

DSA C++

for (int num : arr) { if (num > max_val) max_val = num; }

array with all elements the same

count array counts one number, output array copies original

DSA C++

count[num]++;

When to Use This Pattern

When you need to sort integers with a known small range quickly, use counting sort because it avoids comparisons and sorts in linear time.

Common Mistakes

Mistake: Not using cumulative counts to find correct positions, leading to incorrect output order
Fix: Compute cumulative counts before placing elements to know exact positions

Mistake: Placing elements in output array from start to end, which breaks stability
Fix: Place elements from end to start to maintain stable sorting

Summary

Counting sort sorts numbers by counting their occurrences and placing them in order using these counts.

Use counting sort when sorting integers with a limited range efficiently.

The key insight is using cumulative counts to directly place elements without comparisons.