Counting Sort Explained

Counting Sort is a simple and powerful sorting algorithm that does not use comparisons to arrange elements. Instead of checking which number is bigger or smaller, it works by counting the frequency of each number in the input list. These counts are then used to place the numbers in their correct sorted positions.

Because it avoids comparisons, Counting Sort can be extremely fast, especially when the values are small, non-negative integers that fall within a limited range. This makes it ideal for tasks like sorting marks, ages, ranks, or any data that can be represented as integers. However, it becomes less efficient if the range of numbers is very large compared to the number of elements.

In short, Counting Sort provides predictable linear performance and is perfect for scenarios where the data range is known and manageable.

Quescol 1-Minute Read

Counting Sort is a simple and fast sorting algorithm that works by counting how many times each number appears in a list and then arranging them in the correct order based on those counts. It does not compare elements like other sorting methods. This makes it very quick when the numbers are small and close together. Counting Sort is mostly used for non-negative integers and works best when the range of numbers is not too large. It always performs in O(n + k) time and needs O(k) extra space.

Key Points about Counting Sort

• Works for non-negative integers.
• Does not compare elements.
• Very fast when numbers are small and close.
• Stable sorting algorithm.
• Time Complexity: O(n + k) in all cases.
• Space Complexity: O(k) in all cases.

Let’s Understand in Depth

What is Counting Sort?

Counting Sort is a sorting algorithm that does not compare elements like other sorting methods.
Instead, it works by counting how many times each value appears in the input. It creates an extra array (called the count array) where each index represents a value from the input, and the value at that index tells how many times it occurs. Using this count information, the algorithm arranges all elements in the correct order. Counting Sort is very fast when the range of numbers is small.

Time Complexity of Counting Sort

• Best Case: O(n + k)
• Average Case: O(n + k)
• Worst Case: O(n + k)

n = number of elements
k = range of input values (max value − min value)

Key characteristics of Counting Sort

• It is stable and works in linear time O(n+k)O(n+k), where nn is the number of elements and kk is the range of input values.
• It is not comparison-based, unlike algorithms such as quicksort or mergesort.
• Counting Sort requires auxiliary space proportional to the range of the input values.
• It is most suitable for sorting integers or objects with keys that are small positive integers.
• It cannot handle decimal values or very large ranges efficiently.
• It is used as a subroutine in more complex algorithms like Radix Sort.

Idea Behind Counting Sort

Counting Sort works best when:

• You are sorting non-negative integers (like 0, 1, 2, 3, 4, …).
• The numbers are not too large (for example, all numbers are between 0 and 100).

The main idea is very simple

1. Count how many times each number appears in the list.
2. Use those counts to find the correct position of each number in the sorted order.

It’s like arranging students in order of their roll numbers. If you know exactly how many students have smaller roll numbers than you, you can immediately find your correct position in the line. Counting Sort works using this same idea. It first counts how many times each number appears, then uses those counts to determine where each number should go in the sorted list. This makes Counting Sort very fast and accurate, especially when the numbers are small and not spread across a large range.

The main steps in Counting Sort are

1. Find the maximum value in the input array to determine the size of the count array.
2. Initialize the count array with zeros.
3. Count the occurrences of each value in the input.
4. Compute the cumulative sums in the count array to determine positions.
5. Place elements into the output array based on the count array.
6. Output the sorted array.

Step-by-Step Process of Counting Sort 

Step 1: Find the Largest Number

First, look through your list and find the biggest number in it. This is important because it helps us decide how big our counting array should be.

For example, if your list is [4, 2, 2, 8, 3, 3, 1], the largest number is 8.

So, our counting array should have 9 places (from index 0 to 8).

Step 2: Make a Counting Array

Now we create a new array called count[].

Each index in this array represents a number from input list.

• The size of the count array = (largest number + 1)
• Initially, all values are 0 because we haven’t started counting yet.

For example:

If our largest number is 8 → count = [0, 0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Count Each Element

Now, we look at every number in our input list and increase its count in the count[] array by 1.

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

We go one by one:

• See 4 → increase count[4] by 1 → count[4] = 1
• See 2 → increase count[2] by 1 → count[2] = 1
• See another 2 → increase count[2] again → count[2] = 2
• See 8 → increase count[8] = 1
• See 3 → increase count[3] = 1
• See another 3 → increase count[3] = 2
• See 1 → increase count[1] = 1

So now, our counting array looks like this:

count = [0, 1, 2, 2, 1, 0, 0, 0, 1]

Each position shows how many times that number appears.

Step 4: Modify the Count Array (Cumulative Count)

In this step, we add up the counts from left to right.

This helps us know the actual position of each number in the sorted array.

Let’s add the counts step by step:

count[0] = 0  
count[1] = 1  
count[2] = 1 + 2 = 3  
count[3] = 3 + 2 = 5  
count[4] = 5 + 1 = 6  
count[5] = 6 + 0 = 6  
count[6] = 6 + 0 = 6  
count[7] = 6 + 0 = 6  
count[8] = 6 + 1 = 7

So now, count = [0, 1, 3, 5, 6, 6, 6, 6, 7]

This means:

• Numbers ≤ 1 end at position 1
• Numbers ≤ 2 end at position 3
• Numbers ≤ 3 end at position 5
• Numbers ≤ 8 end at position 7

These positions will help us put each number exactly where it belongs.

Step 5: Build the Output Array

Now we will create a new array called output[] of the same size as the input.

We go through the original array from the end to the beginning (this helps keep the sort stable).

For each number:

1. Look at its count value in count[].
2. Place it at that position in output[].
3. Decrease its count by 1 because we’ve placed one occurrence.

Example using [4, 2, 2, 8, 3, 3, 1]:

• Start from the last number 1: count[1] = 1 → place 1 at position 1 → decrease count[1] → 0
• Next 3: count[3] = 5 → place 3 at position 5 → decrease count[3] → 4
• Next 3: count[3] = 4 → place 3 at position 4 → decrease count[3] → 3
• Next 8: count[8] = 7 → place 8 at position 7 → decrease count[8] → 6
• Next 2: count[2] = 3 → place 2 at position 3 → decrease count[2] → 2
• Next 2: count[2] = 2 → place 2 at position 2 → decrease count[2] → 1
• Next 4: count[4] = 6 → place 4 at position 6 → decrease count[4] → 5

Now output = [1, 2, 2, 3, 3, 4, 8]

Step 6: Copy Back to Original Array

Finally, copy all elements from the output[] array back into the original arr[].

Now your array is completely sorted in ascending order.

Example:

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

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

Example of Counting Sort

Let’s see one more example to understand the Counting Sort process in detail

Input:

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

Step 1: Find the Largest Number

First, we need to find the largest element in the array because it determines how big our counting array should be.

• The largest value in the array is 8.
• Therefore, we will create a counting array of size (8 + 1) = 9 (since we include 0 as an index).

Step 2: Create a Counting Array

We make a new array called count[] of size 9, and initialize all its elements to 0.
Initially:
count[] = [0, 0, 0, 0, 0, 0, 0, 0, 0]

Each index in count[] represents a number in the input range (0 to 8).

Step 3: Count Each Element

Now, we go through each number in the input array and increase its count by 1 in the count[] array.

Let’s count:

• Number 1 appears once → count[1] = 1
• Number 2 appears twice → count[2] = 2
• Number 3 appears twice → count[3] = 2
• Number 4 appears once → count[4] = 1
• Number 8 appears once → count[8] = 1

Now the count[] looks like this:
count[] = [0, 1, 2, 2, 1, 0, 0, 0, 1]

Here, each index shows how many times that number appeared in the input array.

Step 4: Cumulative Count

In this step, we modify the count[] array to store cumulative counts.
Each element at index i will contain the sum of counts up to that index.
This helps us know the final position of each element in the sorted array.

We add the values from left to right:

count[0] = 0  
count[1] = count[1] + count[0] = 1  
count[2] = count[2] + count[1] = 3  
count[3] = count[3] + count[2] = 5  
count[4] = count[4] + count[3] = 6  
count[5] = count[5] + count[4] = 6  
count[6] = count[6] + count[5] = 6  
count[7] = count[7] + count[6] = 6  
count[8] = count[8] + count[7] = 7  

Final cumulative count array:
count[] = [0, 1, 3, 5, 6, 6, 6, 6, 7]

This means:

• Numbers ≤ 1 occupy the first position,
• Numbers ≤ 2 occupy up to the 3rd position,
• Numbers ≤ 3 occupy up to the 5th position, and so on.

Step 5: Build the Output Array

Now we create an output[] array of the same size as the input array.
We go through the input array from the end to the start to maintain stability (order of equal elements).

For each element in arr[]:

1. Look at its value → check its position from the count[].
2. Place it in the output[] array at the correct index (count – 1).
3. Reduce its count by 1 (since one occurrence is now placed).

Let’s do this step by step:

Element	count[value] before	Position in output	count[value] after	output[] after placement
1	1	1 – 1 = 0	0	[1, _, _, _, _, _, _]
3	5	5 – 1 = 4	4	[1, _, _, _, 3, _, _]
3	4	4 – 1 = 3	3	[1, _, _, 3, 3, _, _]
8	7	7 – 1 = 6	6	[1, _, _, 3, 3, _, 8]
2	3	3 – 1 = 2	2	[1, _, 2, 3, 3, _, 8]
2	2	2 – 1 = 1	1	[1, 2, 2, 3, 3, _, 8]
4	6	6 – 1 = 5	5	[1, 2, 2, 3, 3, 4, 8]

Final output[]:
[1, 2, 2, 3, 3, 4, 8]

Step 6: Copy Back

Now, copy all the elements from the output[] array back to the original arr[].

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

Final Sorted Array

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

Thus, the array is successfully sorted using the Counting Sort algorithm.

Time Complexity of Counting Sort

Case	Time Complexity
Best Case	O(n + k)
Average Case	O(n + k)
Worst Case	O(n + k)

Space Complexity of Counting Sort

Case	Space Complexity
Best Case	O(k)
Average Case	O(k)
Worst Case	O(k)

Advantages of Counting Sort

• Predictable Performance:
  The algorithm always performs the same number of steps regardless of input order (no best or worst case difference), ensuring consistent and reliable performance.
• Very Fast for Small Ranges:
  Counting Sort works extremely fast when the range of input numbers (difference between the smallest and largest value) is not very large. It can even outperform comparison-based algorithms like Quick Sort or Merge Sort for such cases.
• Non-Comparison Based Algorithm:
  Unlike most sorting algorithms that compare elements (like Bubble Sort or Merge Sort), Counting Sort directly counts occurrences. This makes it efficient for integer sorting since no element comparisons are needed.
• Stable Sorting Algorithm:
  Counting Sort maintains the order of elements with equal values, meaning if two elements have the same value, their original order remains the same after sorting. This is very useful when sorting objects or records based on one field.
• Good for Sorting Integers and Categorical Data:
  It is ideal for sorting data like grades, marks, age groups, or categories represented by numbers, especially when the range of values is known in advance.
• Linear Time Complexity:
  Counting Sort has a time complexity of O(n + k), which is linear for small values of k (range of numbers). This makes it more efficient than many traditional algorithms for such cases.
• Simple and Easy to Implement:
  The logic of Counting Sort is easy to understand — just count and arrange. It doesn’t require complex recursion or partitioning, making it beginner-friendly and simple to code.
• Efficient for Multiple Pass Sorting:
  Counting Sort can be used as a subroutine in Radix Sort, helping to efficiently sort large numbers by digits or characters.

Disadvantages of Counting Sort (in detail)

• Not an In-Place Algorithm:
  Counting Sort requires additional space to store the count and output arrays, meaning it doesn’t sort the data within the original array itself. This makes it unsuitable for memory-constrained systems.
• Not Suitable for Large Ranges:
  Counting Sort becomes inefficient when the range of numbers (k) is very large compared to the number of elements (n). It requires creating a count array of size k, which can use a lot of memory and make the algorithm slow.
• Works Only for Integers (or Data Convertible to Integers):
  Counting Sort can only handle integers or data that can be easily converted to integer form (like age, marks, etc.). It does not work for floating-point numbers or strings directly without modification.
• High Space Usage:
  Since Counting Sort needs extra arrays — one for counting and one for output — it uses more memory compared to algorithms like Quick Sort or Merge Sort. The space complexity is O(k), which can be large when k is big.
• Not Efficient for Sparse Data:
  If the input values are spread out widely (for example, numbers between 1 and 1,000,000 but only 10 numbers in total), a huge count array is created with mostly unused entries, wasting memory.
• Limited Use Cases:
  Counting Sort is mainly useful for specific tasks like sorting integers or small categories. For general-purpose sorting or when you don’t know the range of numbers, it’s not the best choice.
• Cannot Be Used for Negative Numbers Without Modification:
  By default, Counting Sort does not handle negative numbers since array indices cannot be negative. Extra steps are needed to adjust the algorithm for negative values.

Applications of Counting Sort

• Sorting integers within a small range
  Useful when elements are between a known limit, like 0–100 or 0–1000.
• Sorting characters in strings
  Since ASCII values range from 0 to 255, Counting Sort is ideal for arranging characters.
• Used inside Radix Sort
  Counting Sort is the main stable sorting technique used at each digit level of Radix Sort.
• Frequency counting problems
  Works well when you need to count occurrences of marks, scores, IDs, or age groups.
• Data analysis and statistics
  Used to quickly count and sort values in surveys, votes, grades, or ratings.
• Sorting colors or categories
  Perfect for fixed categories like 0, 1, 2 (e.g., sorting objects by color codes in graphics or image processing).
• Linear-time sorting for competitive programming
  Helps solve problems faster when constraints allow small range values.

Conclusion

Counting Sort is a simple and efficient sorting algorithm that works best for sorting integers within a small and known range. It avoids comparisons by counting the occurrences of each element and then arranging them in order using those counts. The algorithm performs in linear time O(n + k), making it faster than comparison-based sorting methods like Quick Sort or Merge Sort for certain cases. However, it requires extra memory and is not suitable for large ranges or non-integer data. In short, Counting Sort is a great choice when you have limited and closely ranged integer data and want a fast, stable, and easy-to-understand sorting method.