Counting Sort Algorithm

Counting sort is an algorithm used to sort (or order) elements present in a list. It counts the number of times each number appears in the input list. The algorithm then iterates through each number from smallest to largest and places them back in the input list. A slightly complicated algorithm also exists which works for any type of input list like arbitrary objects.

There are simple sorting algorithms like Bubble Sort to some relatively difficult algorithms like quick sort and heap sort. But the idea of this algorithm is the easiest of all. Let us go through the intuition behind it.

Idea Behind the Algorithm

Basic Counting Sort Algorithm for numbers

Let’s say we have an unordered list that contains some numbers, say a thousand numbers. And we also know that each number in the list is between 0 and 5. If we think of how we can sort this kind of data without any programming, we can come up a method easily.

The idea is that we can keep track of how many times number 0 appeared in the list, how many times number 1 appeared in the list and so on until how many times number 5 appeared in the list. Once we note these frequencies, we can create a list by filling each number for the number of times it appeared the in the input list.

For example, let’s say we are given with an input list [3, 0, 2, 3, 2, 1, 2]. We observe that all the numbers are between 0 and 3. So we note the number of times each possible number appeared in the input list:

• Number 0 appeared 1 time
• Number 1 appeared 1 time
• Number 2 appeared 3 times
• Number 3 appeared 2 times

Once we note down the frequencies like we did above, we can go through each possible number in ascending order (0-3 in this case) and fill the number the number of times it appeared in the input list:

• 0 appeared 1 time. Fill the list with 1 0s: [0]
• 1 appeared 1 time. Fill the list with 1 1s: [0, 1]
• 2 appeared 3 times. Fill the list with 3 2s: [0, 1, 2, 2, 2]
• 3 appeared 2 times. Fill the list with 2 3s: [0, 1, 2, 2, 2, 3, 3]

That’s it! All the we have a sorted list for the given unsorted list. This is the idea behind counting sort algorithm. The algorithm seems intuitive for lists with numbers that lie within a specific countable range. In the above example, all the numbers are between 0 and 3. For sorting data like this, it is overkill to use advanced sorting algorithms like quick sort, merge sort etc.

Let’s look at the animation of steps performed in simple counting sort algorithm for the list below:

First we need to look at all the numbers in the input list and find the maximum number. In this case the maximum number is 5. So we create an array with indexes from 0 to 5. Number corresponding to each index can be used to store counts of the corresponding number.

Next we iterate through each number in the list and increment the count in the counts list by 1. For example, if we come across number 5 in the input list, we increment the number at index 5 in counts array by 1. We do this for all the numbers present in the list.

Next we go through count at each index in the counts array in ascending order, and add the number (index number) to the input list number of times it appeared. Each time we overwrite a number to the input list, we decrement the count. So when the count reaches 0, we move on to the next index. Finally after all the counts are decremented to 0, the input list will be sorted.

Advanced Counting Sort Algorithm for objects

The above steps are simple and can be conveniently used to sort lists of numbers that lie in a specific range. But if we were to sort a list of objects with respect one of its fields, say some id attribute, blindly resetting each cell in the input list to the correct number doesn’t work. We need to have a mechanism insert each object in the input list to the correct location in the output list (without overwriting the input list)

In order to achieve that, we need to perform the following operations.

Visit each element in the counts array and store the sum of all counts encountered so far. This sum is known as prefix sum: eg: prefix sum at index 2 = Sum of counts at index 0 + count at index 1 + count at index 2. We can optimally compute the prefix sum at current index by adding the count at current index with the prefix sum of previous index.

Let’s now think about how prefix sums of counts help creating the final array.

In the above example, the prefix sum at index 5 is 10. It means that any number greater than 5 will be inserted from index 10, not before it. It also means that if we visit each element in the unsorted array from left, and encounter number 5, we can insert at position (10-1) = 9th position. And after inserting 5, we decrement count so that next time we need to insert 5, we will insert it at 8th position.

In short, we perform the below steps to create the sorted array using input array and prefix counts array:

• Visit each number in the unsorted list from the end
• Look up the existing prefix sum for the number
• Decrement the prefix sum by 1
• Place the current number at index pointed by the prefix sum

The below animation represents the above steps performed on all the elements in the input list:

You may go through the step by step visualization below for better understanding.

Visualization of Counting Sort Algorithm

Below is the step by step visualization of counting sort algorithm:

Implementing Count Sort Algorithm

# Program to implement Counting sort Algorithm in Python language

# Function to find maximum element in an array
def maxNumInArray(array):
  if len(array) == 0:
    return
  maxElem = array[0]
  for n in array:
    if n > maxElem:
      maxElem = n
  
  return maxElem

def countingSort(array):
    size = len(array)
    output = [0] * size

    # Create counts array with size equal to max element + 1
    maxElem = maxNumInArray(array)
    countsSize = maxElem+1
    # Initialize count array
    count = [0] * countsSize

    # Increment count corresponding to each element in count array
    for i in range(0, size):
        count[array[i]] += 1

    # Store Prefix sums in counts array
    for i in range(1, countsSize):
        count[i] += count[i - 1]

    # Find insert position of each element in counts array
    # Insert the element at correct position
    # And decrement the insert position in counts array
    i = size - 1
    while i >= 0:
      ipos = count[array[i]] - 1
      output[ipos] = array[i]
      count[array[i]] -= 1
      i -= 1

    # Copy the sorted elements into original array
    for i in range(0, size):
        array[i] = output[i]


data = [4, 2, 2, 8, 3, 3, 1]
print("Input Array: ")
print(data)
countingSort(data)
print("Sorted Array in Ascending Order: ")
print(data)

// Program to implement Counting sort Algorithm in Python language

#include <bits/stdc++.h>

// Function to find maximum element in an array
int maxNumInArray(std::vector<int> &array){
  if(array.size() == 0) return 0;
  int maxElem = array[0];
  for(auto n : array)
    if(n > maxElem)
      maxElem = n;
  
  return maxElem;
}

// Function to implement counting sort algorithm
void countingSort(std::vector<int> &array){
    int size = array.size();
    std::vector<int> output(size);

    // Create counts array with size equal to max element + 1
    auto maxElem = maxNumInArray(array);
    // Initialize count array
    std::vector<int> counts(maxElem+1, 0);

    // Increment count corresponding to each element in count array
    for(auto num : array)
        counts[num] += 1;

    // Store Prefix sums in counts array
    for(int i = 0; i < counts.size(); i++)
        counts[i] += counts[i - 1];

    // Find insert position of each element in counts array
    // Insert the element at correct position
    // And decrement the insert position in counts array
    int i = size - 1;
    while(i >= 0){
      int ipos = counts[array[i]] - 1;
      output[ipos] = array[i];
      counts[array[i]] -= 1;
      i -= 1;
    }

    // Copy the sorted elements into original array
    for(int i = 0; i < size; i++)
        array[i] = output[i];
}

// Lets now use counting sort algorithm to sort an array
int main(){
  std::vector<int> data = {1, 5, 3, 5, 2, 1, 4, 2, 3, 5};
  std::cout << "Input Array: ";
  for(int n : data) std::cout << n << " ";
  countingSort(data);
  std::cout << std::endl << "Sorted Array in Ascending Order: ";
  for(int n : data) std::cout << n << " ";
  
  return 0;
}

Characteristics of Counting Sort Algorithm

Time Complexity

Time complexity of counting sort algorithm depends on the size of input list an the range within which all the numbers in the list lie. If the total length of list is assumed to be N, the first iteration in which we store all the counts takes O(N) time. The second iteration of creating prefix sums from counts array takes O(k) time assuming that the numbers lie in range 0 -> k. The third iteration of visiting each number from right to left takes O(N) time. So the total time complexity of counting sort algorithm is O(N) + O(k) + O(N) = O(N+k). The complexity remains same for best, worst and average case scenarios.

Space Complexity

We used an extra list of size k to store the counts and another list of size N to create the output array. So the total space complexity of counting sort algorithm is O(k + N). In the case of simple counting, there is no need of using an auxiliary output array and so the space complexity in that particular case is O(k)

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, while preparing the output array, we iterate from right side and fill any occurrence of the same number from right to left. Hence counting sort algorithm is a kind of stable sort algorithm.

Resources & References

• WikiPedia