Counting sort

Prerequisite knowledge: prefix sums

Reminder

The page introduced here is not radix sort.

This page will briefly introduce counting sort.

Definition

Counting sort (English: Counting sort) is a linear-time sorting algorithm.

Process

Counting sort works by using an additional array $C$, where the $i$-th element is the number of elements in the array $A$ to be sorted whose value equals $i$, and then using array $C$ to place the elements of $A$ in their correct positions.¹

Its process consists of three steps:

1. Count how many times each number occurs;
2. Calculate the prefix sum of the occurrence count of each number;
3. Use the prefix sums of the occurrence counts to calculate the rank of each number from right to left.

Why calculate prefix sums?

Simply placing the elements corresponding to positive values in $C$ into $A$ in order cannot handle the case of repeated elements.

By calculating a prefix sum for each item in the additional array $C$ and combining it with the value of each item, we can determine a unique rank for each repeated element:

The value of each item in the additional array $C$ is the number of repeated elements for that key value, while the prefix sum of that item is the rank of the last repeated element.

If the elements are arranged in reverse order of $A$, it is clear that the sorted array will preserve the original order of $A$ (for equal key values), yielding a stable sorting algorithm.

Properties

Stability

Counting sort is a stable sorting algorithm.

Time complexity

The time complexity of counting sort is $O(n+w)$, where $w$ represents the size of the value domain of the data to be sorted.

Code 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}$$

C++

#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;
}

Python

def counting_sort(a, n, w):
    b = [0] * n
    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]] - 1] = a[i]
        cnt[a[i]] -= 1
    return b

References and notes

Footnotes

1. Counting sort - Wikipedia, the free encyclopedia ↩