C++UCS301
Sorting AlgorithmsC++17

Counting Sort

Counting sort counts occurrences of integer keys in a bounded range, avoiding comparison sorting entirely.

What to understand

  • Frequency arrays
  • Prefix sums
  • Stable output construction
  • Range constraints

Remember this

  1. 1O(n+k) time
  2. 2Useful only when key range k is manageable
  3. 3Can be stable
  4. 4Handles negatives with an offset

Detailed notes

Counting sort replaces comparisons with direct addressing. A frequency array indexed by key records occurrences; prefix sums then reveal where each key's output block ends.

Stable construction scans input from right to left, decrements the key's cumulative count, and places the record at that position. The method is attractive only when key range k is reasonable relative to n.

How it works

  1. 1Find or receive the valid integer key range.
  2. 2Count every key using an offset if needed.
  3. 3Convert frequencies to cumulative positions.
  4. 4Place records into output in reverse input order for stability.

Worked trace

Count bounded keys

[3,1,2,3,0,2]
  1. 1Frequencies for 0..3 become [1,1,2,2].
  2. 2Prefix counts become [1,2,4,6].
  3. 3Scan input right-to-left and decrement each key's position.
  4. 4Equal keys enter output in original relative order.
Result: [0,1,2,2,3,3]

Where it is used

  • Grades, ages, bytes, and bounded identifiers
  • Stable digit sorting inside radix sort
  • Frequency tables and histograms

Common mistakes

  • Allocating an enormous count array for sparse keys
  • Forgetting negative-key offsets
  • Scanning forward during stable output construction

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n+k)O(n+k)O(n+k)O(n+k)

C++ implementation

C++17 reference
main.cpp

Stable counting sort

Prefix sums convert frequencies into final positions. Iterating backward preserves stability.

vector<int> countingSort(const vector<int>& values, int maximum) {
    vector<int> count(maximum + 1, 0), output(values.size());
    for (int value : values) ++count[value];
    for (int i = 1; i <= maximum; ++i) count[i] += count[i - 1];
    for (int i = static_cast<int>(values.size()) - 1; i >= 0; --i) {
        int value = values[i];
        output[--count[value]] = value;
    }
    return output;
}
10 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.