Algorithms · Sorting

Counting Sort

The idea

Sorting coins is not done by comparing pairs. You drop each coin into the tray for its value, then read the trays out smallest to largest. Nobody ever asks "is this coin bigger than that one?" — the trays ARE the order.

The problem

Every sort so far COMPARES items. Counting sort refuses to compare anything. When values live in a small known range (ours: 1-99), just tally how many of each value you have — the tallies alone tell you the final order. Watch the comparison counter: it will stay at zero.

Why it's slow

Counting sort runs in O(n + k) — one pass to tally, one to write, where k is the size of the value range. For a million values between 1 and 99 that is about two million steps, while the best comparison sorts need twenty million. The catch: k must be small and known. Sorting arbitrary words or huge numbers this way would need a tally tray for every possible value — impossible. There is a famous proof that NO comparison-based sort can beat O(n log n); counting sort dodges the law by never comparing at all.

Pseudocode

  1. no comparing at all — we cheat by counting
    Explain this line

    Keep an eye on the comparison counter — it will finish at ZERO.

  2. read each item once and tally how many of each value we saw
    Explain this line

    The read pointer makes exactly one pass: n reads, no decisions.

  3. the tallies tell us exactly where everything belongs
    Explain this line

    Example: two 2s and one 4 means positions 0-1 are 2s, position 2 is the 4.

  4. write the values back in order, smallest first
    Explain this line

    One more pass writes everything home. Total work: about n + k.

Complexity

Best Average Worst Space
O(n + k) O(n + k) O(n + k) O(k)

The rule-breaker: beats every comparison sort by refusing to play their game. Only works when values live in a small, known range — like our 1-99.

Code

python 
def counting_sort(a, max_value=99):
    counts = [0] * (max_value + 1)
    for value in a:
        counts[value] += 1
    k = 0
    for value, count in enumerate(counts):
        for _ in range(count):
            a[k] = value
            k += 1
    return a
java 
void countingSort(int[] a, int maxValue) {
    int[] counts = new int[maxValue + 1];
    for (int value : a) counts[value]++;
    int k = 0;
    for (int value = 0; value <= maxValue; value++) {
        for (int c = 0; c < counts[value]; c++) {
            a[k++] = value;
        }
    }
}
cpp 
void countingSort(std::vector<int>& a, int maxValue) {
    std::vector<int> counts(maxValue + 1, 0);
    for (int value : a) counts[value]++;
    int k = 0;
    for (int value = 0; value <= maxValue; ++value) {
        for (int c = 0; c < counts[value]; ++c) {
            a[k++] = value;
        }
    }
}
javascript 
function countingSort(a, maxValue = 99) {
  const counts = new Array(maxValue + 1).fill(0);
  for (const value of a) counts[value]++;
  let k = 0;
  counts.forEach((count, value) => {
    for (let c = 0; c < count; c++) a[k++] = value;
  });
  return a;
}
dart 
void countingSort(List<int> a, {int maxValue = 99}) {
  final counts = List<int>.filled(maxValue + 1, 0);
  for (final value in a) {
    counts[value]++;
  }
  var k = 0;
  for (var value = 0; value <= maxValue; value++) {
    for (var c = 0; c < counts[value]; c++) {
      a[k++] = value;
    }
  }
}

Quick check