Skip to main content
Linear-Time Sorts

Counting Sort

Count occurrences of each value, then use the counts to place elements directly. O(n+k) where k is the value range. Stable. Works great when k is small relative to n (e.g., sorting grades 0-100).

O(n + k)
·
O(k)

How It Works

Counting sort never compares elements. It allocates a count array indexed by value, tallies how many times each value occurs, converts the tallies into prefix sums so each value knows its starting position in the output, and then walks the input once more, placing each element directly at its computed slot. No decisions, just arithmetic on positions.

Because it sidesteps comparisons entirely, the O(n log n) lower bound does not apply: total work is O(n + k), where k is the size of the value range. That is a genuine win when k is modest — sorting exam scores, ages, or characters — and a disaster when k is huge (sorting a handful of 64-bit values would need an astronomically large count array). Iterating the input backwards during placement preserves the relative order of equal keys, and that stability is precisely what radix sort depends on when it uses counting sort per digit.

Step-by-Step Visualization

Counting sort: count occurrences
4
0
2
1
2
2
8
3
3
4
3
5
1
6
Count[0,1,2,2,1,0,0,0,1]
1/3

Code

Java
static int[] countingSort(int[] arr) {
  int max = 0;
  for (int x : arr) max = Math.max(max, x);
  int[] count = new int[max + 1];
  for (int x : arr) count[x]++;

  List<Integer> result = new ArrayList<>();
  for (int i = 0; i <= max; i++)
    for (int j = 0; j < count[i]; j++) result.add(i);
  return result.stream().mapToInt(Integer::intValue).toArray();
}

Tips & Gotchas

1Count occurrences of each value in a count array
2Build output by iterating through count array
3Only works when the range of values (k) is reasonable

Practice Problems

  • 1Sort Colors
  • 2Sort Characters By Frequency
  • 3Height Checker
  • 4Relative Sort Array

About the Linear-Time Sorts Pattern

These bypass the O(n log n) barrier by NOT comparing elements. Instead, they use the values directly. The catch: they only work when values fall within a known, bounded range.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

  • Sort Colors
  • Kth Largest Element
  • Merge Intervals
  • Largest Number
  • Sort List
  • Meeting Rooms

Frequently Asked Questions

How does counting sort escape the O(n log n) lower bound?

The lower bound only governs algorithms whose information comes from pairwise comparisons — their decision trees need log(n!) depth. Counting sort reads values as array indices instead of comparing them, so the bound simply does not apply; the price is the O(k) dependence on the value range.

What makes counting sort stable, and why does it matter?

After prefix sums, each value has a reserved block of output positions; filling from the end of the input while decrementing positions keeps equal elements in their original relative order. Stability matters chiefly because radix sort applies counting sort per digit and relies on earlier digit orderings surviving later passes.

When is counting sort the wrong tool despite integer input?

When the value range k dwarfs n — a million elements spanning 64-bit integers would need an impossibly large count array dominated by zeros. In that regime, use radix sort to break values into small digits, or fall back to an O(n log n) comparison sort.