Counting Sort

Counting sort is a non-comparative sorting algorithm. It sorts an array by counting occurrences of each unique element. It partially hashes the count of unique elements and then performs calculations to find the index of each element in the final, sorted array. It is quite a fast algorithm but unsuitable for large datasets. It is used as a subroutine inside radix sort.

Counting Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

Counting Sort Example

Suppose we have the array: (6, 3, 2, 7, 4, 5, 4, 2). We will sort it using the counting sort algorithm.

• maxm = 7
• minm = 2
• range = 6
• count and output are initialized with zeros.

• count array after computing the count of all the elements.

• count array after cumulation of the sum of elements.

• First Iteration: A[7]=2

• Second Iteration: A[6]=4

• Third Iteration: A[5]=5

• Fourth Iteration: A[4]=4

• Fifth Iteration: A[3]=7

• Sixth Iteration: A[2]=2

• Seventh Iteration: A[1]=3

• Eighth Iteration: A[0]=6

Finally, we store the output array inside A and get the sorted array - 2, 2, 3, 4, 4, 5, 6, 7.

Counting Sort Algorithm Implementation

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

int minm(int arr[], int n) {
  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

void countingSort(int arr[], int n) {
  int min = minm(arr, n);
  int max = maxm(arr, n);
  int range = max - min + 1;
  int count[range] = {};
  int output[n];
  for (int i = 0; i < n; i++) count[arr[i] - min]++;

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

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

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

int main() {
  int n = 7;
  int arr[7] = {3, 5, 1, 1, 4, 2, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  countingSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

This implementation also works for negative numbers.

Counting Sort Algorithm Complexity

Time Complexity

• Average Case

Counting Sort iterates through all the n items twice and iterates through the count array once. So, it has a time complexity of O(n + b) where b is the range of input. Since b is often small, the counting sort’s time complexity is said to be of the order of [Big Theta]: O(n).

• Worst Case

The worst-case time complexity is [Big O]: O(n).

• Best Case

The best-case time complexity is [Big Omega]: O(n). It is the same as the worst-case time complexity.

Space Complexity

Space Complexity for the counting sort algorithm is O(n+b), where b is the range of input. It comes from count &output arrays. Sometimes b can be larger than n, but if b is small, the time complexity is said to be of O(n).