Skip to content

Counting Sort

This page assumes you know prefix sums.

Note

This page is not about radix sort.

This page gives a brief introduction to counting sort.

Definition

Counting sort is a linear-time sorting algorithm.

Procedure

Counting sort uses an extra array \(C\) whose \(i\)-th element is the number of elements equal to \(i\) in \(A\), the array to be sorted. It then uses \(C\) to put the elements of \(A\) into their correct positions.1

It works in three steps:

  1. Count how many times each number occurs;
  2. Compute the prefix sums of these counts;
  3. Using the prefix sums of the counts, compute the rank of each number, going from right to left.

Why compute prefix sums

Rebuilding the array from the counts is enough to sort bare keys, duplicates included. To rearrange the original records stably, use the prefix sums of the counts to determine the output positions.

Computing the prefix sum at every entry of the extra array \(C\) and combining it with the value of the entry itself gives each of the duplicate elements a unique rank:

The value of an entry of \(C\) is the number of duplicate elements with that key, and the prefix sum at that entry is the rank of the last of these duplicates.

If we place the elements in the reverse of their order in \(A\), the sorted array clearly keeps the original order of \(A\) (among elements with the same key), so we get a stable sorting algorithm.

counting sort animate example

Properties

Stability

Counting sort is a stable sorting algorithm.

Time complexity

Counting sort runs in \(O(n+w)\), where \(w\) is the size of the value range of the data to be sorted.

Implementation

Pseudocode

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ positive integers no greater than } w. \\ 2 & \textbf{Output. } \text{Array }A\text{ after sorting in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }i\gets0\textbf{ to }w\\ 5 & \qquad \textit{cnt}[i]\gets0\\ 6 & \textbf{for }i\gets1\textbf{ to }n\\ 7 & \qquad \textit{cnt}[A[i]]\gets\textit{cnt}[A[i]]+1\\ 8 & \textbf{for }i\gets1\textbf{ to }w\\ 9 & \qquad \textit{cnt}[i]\gets \textit{cnt}[i]+\textit{cnt}[i-1]\\ 10 & \textbf{for }i\gets n\textbf{ downto }1\\ 11 & \qquad B[\textit{cnt}[A[i]]]\gets A[i]\\ 12 & \qquad \textit{cnt}[A[i]]\gets \textit{cnt}[A[i]]-1\\ 13 & \textbf{return } B \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <cstring>
constexpr int MAXN = 1010;
constexpr int MAXW = 100010;

int cnt[MAXW], b[MAXN];

int* counting_sort(int* a, int n, int w) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
  return b;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def counting_sort(a, n, w):
    b = [0] * (n + 1)
    cnt = [0] * (w + 1)
    for i in range(1, n + 1):
        cnt[a[i]] += 1
    for i in range(1, w + 1):
        cnt[i] += cnt[i - 1]
    for i in range(n, 0, -1):
        b[cnt[a[i]]] = a[i]
        cnt[a[i]] -= 1
    return b

References and notes