C++ Program for Counting Sort with Example and Explanation

A C++ program for counting sort uses an array to count occurrences of each number, then reconstructs the sorted array; for example, void countingSort(int arr[], int n) { int max = *max_element(arr, arr + n); int count[max + 1] = {0}; for (int i = 0; i < n; i++) count[arr[i]]++; int index = 0; for (int i = 0; i <= max; i++) while (count[i]--) arr[index++] = i; } sorts the array in ascending order.

Examples

Inputarr = {4, 2, 2, 8, 3, 3, 1}, n = 7

OutputSorted array: 1 2 2 3 3 4 8

Inputarr = {5, 4, 3, 2, 1}, n = 5

OutputSorted array: 1 2 3 4 5

Inputarr = {1, 1, 1, 1}, n = 4

OutputSorted array: 1 1 1 1

How to Think About It

To sort numbers using counting sort, first find the largest number to know the range. Then count how many times each number appears using a counting array. Finally, rebuild the sorted array by writing each number as many times as it appeared.

Algorithm

1

Find the maximum value in the input array.

2

Create a counting array of size max+1 and initialize all counts to zero.

3

Count the occurrences of each number in the input array.

4

Iterate over the counting array and overwrite the input array with sorted numbers based on counts.

5

Print or return the sorted array.

Code

cpp

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

void countingSort(int arr[], int n) {
    int max = *max_element(arr, arr + n);
    int count[max + 1] = {0};

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output

Sorted array: 1 2 2 3 3 4 8 

Dry Run

Let's trace the array {4, 2, 2, 8, 3, 3, 1} through the counting sort code.

1

Find max value

Maximum value in array is 8.

2

Initialize count array

Create count array of size 9 (0 to 8) with all zeros.

3

Count occurrences

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

4

Rebuild sorted array

Write numbers back: 1 once, 2 twice, 3 twice, 4 once, 8 once.

5

Final sorted array

Sorted array is {1, 2, 2, 3, 3, 4, 8}.

Number	Count
0	0
1	1
2	2
3	2
4	1
5	0
6	0
7	0
8	1

Why This Works

Step 1: Counting occurrences

The code uses a count array where each index represents a number, and the value at that index is how many times it appears in the input.

Step 2: Rebuilding sorted array

By iterating over the count array and writing each number as many times as counted, the original array becomes sorted.

Step 3: No comparisons needed

Counting sort does not compare elements but uses counting, making it very fast for numbers in a small range.

Alternative Approaches

Using std::vector for dynamic count array

cpp

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

void countingSort(vector<int>& arr) {
    int max = *max_element(arr.begin(), arr.end());
    vector<int> count(max + 1, 0);

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

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i;
        }
    }
}

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

Using vector allows dynamic sizing and safer memory management but may have slight overhead.

Counting sort with output array

cpp

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

void countingSort(int arr[], int n) {
    int max = *max_element(arr, arr + n);
    int count[max + 1] = {0};
    int output[n];

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

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

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

This stable version uses an output array and prefix sums but requires extra space.

Complexity: O(n + k) time, O(k) space

Time Complexity

Counting sort runs in O(n + k) where n is the number of elements and k is the range of input values, because it counts occurrences and then reconstructs the array.

Space Complexity

It uses O(k) extra space for the count array, which depends on the maximum value in the input.

Which Approach is Fastest?

Counting sort is fastest when the range k is not much larger than n; otherwise, comparison-based sorts may be better.

Approach	Time	Space	Best For
Basic counting array	O(n + k)	O(k)	Small range integers
Vector-based count array	O(n + k)	O(k)	Dynamic or unknown range
Stable counting sort with output array	O(n + k)	O(n + k)	When stability is needed