Counting Sort

Introduction

Counting Sort is a non-comparison based sorting algorithm.

Unlike Bubble Sort, Merge Sort, Quick Sort, etc., it does not compare elements with each other.

Instead, it:

1. Counts the frequency of each element.
2. Uses these frequencies to determine the correct position of elements.
3. Constructs the sorted array.

Counting Sort is efficient when the range of input values is not very large.

Idea Behind Counting Sort

Suppose,

arr = [4, 2, 2, 8, 3, 3, 1]

Observe that:

• 1 appears once
• 2 appears twice
• 3 appears twice
• 4 appears once
• 8 appears once

If we know these frequencies, then the sorted array can be reconstructed as:

[1, 2, 2, 3, 3, 4, 8]

This is exactly what Counting Sort does.

Terminology

Let,

n = number of elements

maxVal = maximum element
minVal = minimum element

k = range of elements
  = maxVal - minVal + 1

Example:

arr = [4,2,2,8,3,3,1]

Then,

n = 7

maxVal = 8
minVal = 1

k = 8 - 1 + 1
  = 8

---

Steps of Counting Sort

Suppose,

arr = [4,2,2,8,3,3,1]

Step 1: Find maximum element

maxVal = 8

Create count array:

vector<int> cnt(maxVal + 1, 0);

Initially,

Index : 0 1 2 3 4 5 6 7 8

Count : 0 0 0 0 0 0 0 0 0

Step 2: Count frequencies

Traverse array:

for(int x : arr)
    cnt[x]++;

After counting:

Index : 0 1 2 3 4 5 6 7 8

Count : 0 1 2 2 1 0 0 0 1

Meaning:

1 occurs 1 time

2 occurs 2 times

3 occurs 2 times

4 occurs 1 time

8 occurs 1 time

Step 3: Reconstruct sorted array

Traverse count array.

If

cnt[i] = 3

then insert i three times.

Example:

i=1 -> insert once

i=2 -> insert twice

i=3 -> insert twice

i=4 -> insert once

i=8 -> insert once

Sorted array:

[1,2,2,3,3,4,8]

---

Implementation (Simple Version)

void countingSort(vector<int>& arr)
{
    int mx = *max_element(arr.begin(), arr.end());
    vector<int> cnt(mx + 1, 0);
    for(int x : arr)
        cnt[x]++;

    int idx = 0;
    for(int i = 0; i <= mx; i++)
    {
        while(cnt[i] > 0)
        {
            arr[idx++] = i;
            cnt[i]--;
        }
    }
}

Dry Run

Input:

arr = [4,2,2,8,3,3,1]

Count array:

Index : 0 1 2 3 4 5 6 7 8

Count : 0 1 2 2 1 0 0 0 1

Reconstruction:

i=0 -> add nothing

i=1 -> add 1

arr = [1]

----------------

i=2 -> add 2 twice

arr = [1,2,2]

----------------

i=3 -> add 3 twice

arr = [1,2,2,3,3]

----------------

i=4 -> add 4

arr = [1,2,2,3,3,4]

----------------

i=5 -> nothing

i=6 -> nothing

i=7 -> nothing

----------------

i=8 -> add 8

arr = [1,2,2,3,3,4,8]

---

Time Complexity & Space Complexity

Time Complexity

Let,

n = size of array

k = range of values

Step 1 Find maximum

O(n)

Step 2 Count frequencies:

for(int x : arr)
    cnt[x]++;

Runs n times.

Time = O(n)

Step 3 Traverse count array:

for(int i=0;i<=maxVal;i++)

Runs k times.

Time = O(k)

Step 4 Reconstruct array:

while(cnt[i] > 0)

This loop looks nested, but total executions are exactly n.

Why?

Because:

Total frequencies

= cnt[0] + cnt[1] + ...

= n

Each execution decreases frequency by one.

So,

Time = O(n)

Overall Complexity

O(n) + O(n) + O(k) + O(n) = O(3n + k) = O(n + k)

Final:

Time Complexity

= O(n + k)

where

k = maxVal - minVal + 1

Space Complexity

We use:

Count Array

vector<int> cnt(k);

Space:

O(k)

Output Array (Stable Version)

vector<int> output(n);

Space:

O(n)

Total Space

Stable Counting Sort:

O(n+k)

Simple In-place Reconstruction:

O(k)

---

Stable Counting Sort

The previous implementation is not stable.

Stable means:

Equal elements preserve their original relative order.

Example:

Input

2A 1 2B

Output

1 2A 2B

The order of

2A before 2B

should remain same.

Counting Sort can be made stable.

Steps of Stable Counting Sort

Step 1 Count frequencies.

cnt[x]++;

Step 2 Convert count array into prefix sums.

for(int i=1;i<=mx;i++)
    cnt[i]+=cnt[i-1];

Example:

Frequency:

0 1 2 2 1 0 0 0 1

Prefix Sum:

0 1 3 5 6 6 6 6 7

Meaning:

1 ends at index 0

2 ends at index 2

3 ends at index 4

4 ends at index 5

8 ends at index 6

Step 3 Traverse original array from right to left.

output[cnt[arr[i]]-1]=arr[i];

cnt[arr[i]]--;

This preserves order and makes sorting stable.

---

Advantage , Disadvantage & Applications

Advantages

1. Very fast when range is small.
2. Time complexity:

O(n+k)

which can be better than:

O(n log n)

3. Stable sorting is possible.
4. Useful as a subroutine in:

Radix Sort

Bucket Sort

Disadvantages

1. Works only for integers or discrete values.
2. Not suitable when:

maxVal - minVal

is very large.

Example:

arr = [1, 1000000000]

Need:

10^9 sized count array

which is impractical.

3. Extra memory required.

When to Use Counting Sort

Use Counting Sort when:

1. Elements are integers.

2. Range of elements is small.

3. O(n log n) sorting is slower than O(n+k).

4. Stable sorting is required.

Applications

1. Radix Sort
2. Bucket Sort
3. Frequency Counting
4. Histogram Construction
5. Sorting ages, marks, grades
6. Competitive Programming problems with small value ranges

Example:

1 <= arr[i] <= 100000

which is exactly the condition where Counting Sort becomes very efficient.