Counting sort

Counting sort puts numbers, or records with a number as their key, in order by counting how many times each value occurs. It works when the values are small whole numbers, such as marks from 0 to 100; for large or arbitrary values, use std::sort.

Explanation

A teacher has six marks from 0 to 3: 2, 0, 3, 2, 0, 2. Instead of sorting them by comparing, she counts how many times each mark occurs, then writes each mark out as many times as it was counted.

With six marks it makes no difference. With 10^6 marks from 0 to 100, std::sort makes about n \log_2 n \approx 10^6 \cdot 20 = 2 \cdot 10^7 comparisons (time complexity), while counting reads each mark once and then goes through 101 counts: about 10^6 + 101 steps.

The counts are an array with one cell for each possible mark, and the mark is the number of its cell.

Fig. 1. Each mark adds 1 to its cell, then each value is written out as many times as it was counted.

Usually each mark belongs to a pupil. Eight pupils, A to H, have marks from 0 to 4, and the teacher wants the list of pupils in order of their marks. Each pupil is a record, and the mark is its key.

Counting still works: one pupil has 0, two have 1, one has 2, three have 3 and one has 4. But writing out "3, 3, 3" loses which pupils had those marks: the counts don't remember that A, D and G are the ones with 3. Where does G go in the sorted list?

The counts used the mark as the number of the cell, so the same trick seems to work for pupils: put each pupil into the output cell with their mark's number. G has mark 3 and goes to cell 3. But A and D have mark 3 as well, so all three land in cell 3 and G overwrites them.

Fig. 2. Using the mark as the cell number: A, D and G all land in cell 3.

So the question is how many cells come before the pupils with mark 3. Every pupil with a smaller mark comes before them: one with 0, two with 1 and one with 2, so 4 pupils. The pupils with mark 3 then take cells 4, 5 and 6, a block of 3 cells, as many as their count.

Each mark's block starts where the previous block ends: the block of 0 starts at 0, the block of 1 at 0 + 1 = 1, the block of 2 at 1 + 2 = 3, the block of 3 at 3 + 1 = 4 and the block of 4 at 4 + 3 = 7. These starts are a running total of the counts, a prefix sum.

Now read the pupils from left to right and put each into the next free cell of its block. A is the first with mark 3 and takes cell 4, D takes cell 5 and G takes cell 6. Every block has exactly as many cells as pupils, so no two pupils share a cell.

This is counting sort: count the keys, find where the block of each key starts, then place each record into the next free cell of its block. No record is compared with another.

Count: every count starts at 0.

Count: A has mark 3, so the count of 3 becomes 1. The blue pupil is the one being read.

Count: B has mark 1, so the count of 1 becomes 1.

Count: C has mark 4, so the count of 4 becomes 1.

Count: D has mark 3, so the count of 3 becomes 2.

Count: E has mark 0, so the count of 0 becomes 1.

Count: F has mark 1, so the count of 1 becomes 2.

Count: G has mark 3, so the count of 3 becomes 3.

Count: H has mark 2, so the count of 2 becomes 1.

Find starts: the block of 0 starts at cell 0 and has 1 cell, as many as the count of 0. The shaded cells of the bottom row are the block.

Find starts: the block of 1 starts at 0 + 1 = 1, right after the block of 0, and has 2 cells.

Find starts: the block of 2 starts at 1 + 2 = 3, right after the block of 1, and has 1 cell.

Find starts: the block of 3 starts at 3 + 1 = 4, right after the block of 2, and has 3 cells.

Find starts: the block of 4 starts at 4 + 3 = 7, right after the block of 3, and has 1 cell.

Place: A has mark 3 and goes to cell 4, the first cell of the block of 3; the next free cell of 3 becomes 5.

Place: B has mark 1 and goes to the next free cell of the block of 1, cell 1; the next free cell of 1 becomes 2.

Place: C has mark 4 and goes to the next free cell of the block of 4, cell 7; the next free cell of 4 becomes 8.

Place: D has mark 3 and goes to the next free cell of the block of 3, cell 5; the next free cell of 3 becomes 6.

Place: E has mark 0 and goes to the next free cell of the block of 0, cell 0; the next free cell of 0 becomes 1.

Place: F has mark 1 and goes to the next free cell of the block of 1, cell 2; the next free cell of 1 becomes 3.

Place: G, the third pupil with mark 3, goes to cell 6, after A and D; the next free cell of 3 becomes 7.

Place: H has mark 2 and goes to the next free cell of the block of 2, cell 3; the next free cell of 2 becomes 4.

The sorted list is E, B, F, H, A, D, G, C; A, D and G keep their input order.

1/23

Fig. 3. Step through counting sort with the buttons. The shaded areas of the bottom row are the blocks of the keys.

The sorted list is E, B, F, H, A, D, G, C. A, D and G keep their order from the input, because pupils with the same mark fill their block in the order they were read. A sort that keeps records with equal keys in input order is called stable.

The run took 8 steps to count, 5 to find the starts and 8 to place: 8 + 5 + 8 = 21 steps. For $n$ records with keys from 0 to $K$ that is 2n + (K + 1) steps, and without the constant factors, O(n + K) time. There is one count for every possible key, so K must fit in memory: the counts for K = 10^7 take 40 MB.

Sorting letters

A string of lowercase letters is a list of keys from a range of 26 values. Letters have consecutive codes, so c - 'a' turns the letter c into a cell number from 0 to 25, and 26 counts are enough:

vector<int> cnt(26, 0);
for (char c : s) cnt[c - 'a']++;          // count

Writing the letters out from cell 0 to cell 25 gives the sorted string. Subtracting 'a' shifts the keys so that they start at 0; the same shift makes negative keys usable.

Implementation

The records have names name[i] and keys key[i], for i from 0 to n - 1, and every key is from 0 to K. The count of key v is cnt[v]. The block of key v is the part of the output array out that its records fill. start[v] begins at the first cell of the block and then holds the next free cell of the block: it moves one cell to the right each time a record is placed there.

1. Count: for each record, add 1 to cnt[key[i]] (for the pupils, cnt becomes 1 2 1 3 1).

2. Find starts: start[0] = 0, and each next start is the previous start plus the previous count (start becomes 0 1 3 4 7).

3. Place: for i from 0 to n - 1, put name[i] into out[start[key[i]]] and move start[key[i]] one cell right (A goes to out[4], then start[3] becomes 5).

The input has n and K on the first line, then n lines with a name and a key. For the eight pupils it is:

8 4
A 3
B 1
C 4
D 3
E 0
F 1
G 3
H 2

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n, K;
    cin >> n >> K;
    vector<string> name(n);
    vector<int> key(n);
    for (int i = 0; i < n; i++) {
        cin >> name[i] >> key[i];
    }

    // count
    vector<int> cnt(K + 1, 0);
    for (int i = 0; i < n; i++) {
        cnt[key[i]]++;
    }

    // find starts
    vector<int> start(K + 1, 0);
    for (int v = 1; v <= K; v++) {
        start[v] = start[v - 1] + cnt[v - 1];
    }

    // place
    vector<string> out(n);
    for (int i = 0; i < n; i++) {
        out[start[key[i]]] = name[i];
        start[key[i]]++;                     // next free cell of this block
    }

    for (int i = 0; i < n; i++) {
        cout << out[i] << (i < n - 1 ? ' ' : '\n');
    }
}

The program uses O(n + K) memory for cnt, start and out.

To sort by decreasing keys, lay the blocks out from key K down to 0: start[K] = 0, and start[v] = start[v + 1] + cnt[v + 1] for v from K - 1 down to 0. For the pupils, start[4] to start[0] become 0, 1, 4, 5, 7, and the output is C, A, D, G, H, B, F, E. The records are still placed from left to right, so equal keys keep their input order.

Sorting plain numbers

Without records, start and out are not needed. The input is n and K, then n numbers from 0 to K.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, K;
    cin >> n >> K;
    vector<int> cnt(K + 1, 0);

    // count
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    // write out
    for (int v = 0; v <= K; v++) {   // for decreasing order: for (int v = K; v >= 0; v--)
        for (int j = 0; j < cnt[v]; j++) {
            cout << v << ' ';
        }
    }
    cout << '\n';
}

Counting sort or std::sort

Counting sort keeps K + 1 counts in memory, so the choice depends on $K$ as well as $n$. As a rule of thumb, counting sort pays off when $K$ is not much larger than $n$ and at most about 10^7.

Common mistakes

• Using negative keys as cell numbers. The keys −2, 3, −2 write to cnt[-2]. Subtract the smallest key before counting (or add a fixed offset, such as 10^4 for values from -10^4 to 10^4) and add it back when printing.

• Reading the records from right to left while filling the blocks from their starts. For the pupils this gives E, F, B, H, G, D, A, C: the 1s and the 3s come out in reverse input order. Read from left to right filling each block from its first cell, or from right to left filling it from its last cell, never a mix.

• Not clearing cnt between test cases. If one class has marks 5 and 7 and the next has mark 6, the second class is printed as 5, 6, 7. Declare cnt inside the loop over test cases, or fill it with zeros.

Similar algorithms

Coordinate compression is for values that are large but few and must be used as cell numbers, for example as counters. It sorts them once, then renumbers them 0, 1, 2 and so on; it is not a way around sorting.

A map counts large or scattered values with cnt[x]++ and lists them in sorted order, at O(\log m) per value for $m$ different values.

Radix sort sorts large integers by running a stable counting sort on each digit, from the last digit to the first. The same idea sorts records by two keys: sort by the second key first, then stably by the first.

Practice