cf.completefrontend
SORTING · CORE

Counting sort

Sort small whole numbers by counting how many times each value appears, then writing the values back in order.

Time O(n + k)Space O(n + k)5 practice problemsStep-through picture

The idea

Counting sort never compares two items. Instead, it uses the values themselves as positions. If every item is a whole number from 0 to maxValue, make an array counts with one slot per possible value, and go through the list adding 1 to counts[value] for each item.

Now counts says, for example, "two 1s, one 2, zero 3s, one 4". Walk through the values from smallest to largest and write each value out as many times as it was counted. The result is sorted.

This takes O(n + k) time, where k is the number of possible values. When k is small, like star ratings from 1 to 5 or ages from 0 to 120, that beats any comparison sort. When k is huge, like any 32-bit number, the counts array would be too big.

An everyday example

Tallying votes on a whiteboard

A class votes for its favorite day of the week. Instead of sorting the paper ballots, the teacher draws seven columns on the board, Monday to Sunday, and makes a tally mark under the right day for each ballot. To read the votes out in order, she goes column by column: "Monday, Monday, Tuesday, Thursday...", saying each day once per tally mark.

How the example maps to the code
In the exampleIn the code
The columns on the boardcounts, one slot per value
A tally mark for a ballotcounts[value]++
Going through the columns in orderfor (let value = 0; value <= maxValue; value++)
Reading a day once per markPushing value counts[value] times

From the slow way to counting sort

  1. Every sort so far compares two items at a time. There is a proven limit to that: any method that learns the order only through comparisons needs about n × log₂ n comparisons in the worst case. To beat it, we must learn about the order some other way.
  2. Suppose the items are small whole numbers, like scores from 0 to 4. Then the value itself tells us where it goes: all the 0s come first, then all the 1s, and so on. We don't need to compare 3 with 1; we only need to know how many 0s, 1s, 2s, 3s, and 4s there are.
  3. Counting is one pass. Make an array counts with one slot per possible value, all zero, and add 1 to counts[value] for each item. Array slots are already in order, slot 0 before slot 1, so the counts are sorted by value for free.
  4. To produce the output, walk value from 0 to maxValue and write it out counts[value] times. The cost is one pass over the n items plus one pass over the k possible values. Count each value, then write the values out in slot order: that loop is counting sort.

How it works

  1. Create counts, an array of maxValue + 1 zeros.
  2. For each value in the list, add 1 to counts[value].
  3. Walk value from 0 to maxValue.
  4. Push value into result counts[value] times.
  5. Return result.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function countingSort(items, maxValue) {
  2. const counts = new Array(maxValue + 1).fill(0);
  3. for (const value of items) {
  4. counts[value]++;
  5. }
  6. const result = [];
  7. for (let value = 0; value <= maxValue; value++) {
  8. for (let c = 0; c < counts[value]; c++) {
  9. result.push(value);
  10. }
  11. }
  12. return result;
  13. }

How fast it is

TimeO(n + k)
Extra memoryO(n + k)

k is maxValue + 1, the number of possible values. Counting touches each of the n items once, and writing out visits each of the k counters once.

  • Best caseO(n + k)

    Every input costs the same: one pass over the n items and one over the k = maxValue + 1 slots. With star ratings, k is tiny and it is effectively O(n).

  • Average caseO(n + k)

    The order of the input doesn't matter at all. Only n and k do.

  • Worst caseO(n + k)

    When k is much bigger than n, like 10 items with values up to 1,000,000, the slot walk dominates: a million checks to sort ten numbers.

Common mistakes

  • Using it on negative numbers. counts[-3] is not an array slot. Shift every value by the minimum first (value - min), then shift back.
  • Using it when the range is huge, such as timestamps in milliseconds. The counts array would need billions of slots.
  • Forgetting the + 1 in maxValue + 1, so the largest value has no counter.
  • Rebuilding only the keys when sorting records. The rest of each record is lost; use the stable placement version.

When to use it

Look for these clues in a problem:

  • The values are whole numbers in a small known range, such as ratings, ages, scores out of 100, or priority levels.
  • You need O(n) sorting and the range of values is not much bigger than the number of items.
  • You need to sort records by a small integer key while keeping equal keys in their original order.

Check yourself

Answer each one in your head first, then open it.

How can counting sort beat the n × log₂ n limit for sorting?

That limit only applies to sorts that learn the order by comparing items. Counting sort never compares; it uses each value as an array index, which a comparison sort can't do.

How many slots does counts need for values from 0 to 99?

100, which is maxValue + 1. Slot 99 must exist for the value 99.

Why is counting sort a bad choice for 10 timestamps in milliseconds?

Today's timestamps are about 1.8 trillion, so counts would need that many slots. The k part of O(n + k) swamps the n = 10 items.

Why does this simple version not need to worry about stability for plain numbers?

Equal numbers can't be told apart, so their order doesn't matter. Stability only matters when items carry other data, like records with the same key.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

After the counting loop, the rule is: counts[v] equals the number of items equal to v, for every v from 0 to maxValue. It starts true with all zeros and no items seen, and each counts[value]++ keeps it true for one more item.

The writing loop keeps a second rule: result holds every item with a value smaller than value, in sorted order. Writing value exactly counts[value] times adds all items equal to value, and they belong right after everything smaller. So when value passes maxValue, result holds every item, in order.

Both loops end: the first after n items, the second after maxValue + 1 slots, and each inner loop after counts[value] pushes. The total number of pushes is exactly n, so the output has the same length as the input. All of this depends on one promise from the caller: every item is a whole number from 0 to maxValue.

Going deeper

3 more ideas

Why it works without comparing

Array indexes are already in order: slot 0 comes before slot 1, which comes before slot 2. Counting puts each value's tally in its own slot, so walking the slots from left to right visits the values in sorted order. Nothing is ever compared with anything.

The stable version for records

To sort records (like tasks with a priority) rather than bare numbers, turn counts into starting positions: a running total where start[v] is how many items have a key smaller than v. Then walk the records in their original order and place each one at start[key], adding 1 afterwards. Items with the same key land in their original order, so the sort is stable. Radix sort depends on this.

How long it takes

Counting is one pass over the n items, and writing out is one pass over the k slots plus the n items: O(n + k) time and O(k) extra space for counts. For star ratings, k is 6, so it is just O(n). For values up to a billion, k is a billion, which is far too much memory.

Work it by hand

Every step in a table, with why

Sort 7 scores from 0 to 4. Watch counts fill up, then result grow, including a value (2) that never appears.

items = [3, 0, 4, 3, 1, 4, 3], maxValue = 4

StepPhasevaluecountsresultWhat happensWhy
1Count3[0, 0, 0, 1, 0][]counts[3]++counts starts as maxValue + 1 = 5 zeros. The first item adds one 3.
2Count0[1, 0, 0, 1, 0][]counts[0]++A 0 uses slot 0. Values are indexes, so 0 needs no special case.
3Count4[1, 0, 0, 1, 1][]counts[4]++4 is maxValue, the last slot. This is why the array has maxValue + 1 slots.
4Count3[1, 0, 0, 2, 1][]counts[3]++A repeat just raises the count.
5Count1[1, 1, 0, 2, 1][]counts[1]++One 1 so far.
6Count4[1, 1, 0, 2, 2][]counts[4]++The second 4.
7Count3[1, 1, 0, 3, 2][]counts[3]++The counting pass is done after 7 steps, one per item. No two items were ever compared.
8Write0[1, 1, 0, 3, 2][0]Push 0 onceWalk value from 0. counts[0] is 1, so the inner loop pushes one 0.
9Write1[1, 1, 0, 3, 2][0, 1]Push 1 onceSlot 1 comes right after slot 0, so the output stays in order.
10Write2[1, 1, 0, 3, 2][0, 1]counts[2] is 0: skipThe inner loop runs zero times. Empty slots still cost one check each, which is the k in O(n + k).
11Write3[1, 1, 0, 3, 2][0, 1, 3, 3, 3]Push 3 three timesThree 3s were counted, so three are written.
12Write4[1, 1, 0, 3, 2][0, 1, 3, 3, 3, 4, 4]Push 4 twice; loop endsvalue reaches maxValue, the last slot. The next check, 5 <= 4, ends the loop.

It returns [0, 1, 3, 3, 3, 4, 4] after 7 counting steps and 5 slot visits: n + k = 7 + 5 steps, with zero comparisons between items.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Counting sortO(n + k)O(n + k)Values are whole numbers in a small range, like ratings, ages, or letters, and k is not much bigger than n.
Radix sortO(d × n)O(n)Values are whole numbers with a large range but few digits, such as 32-bit IDs. It runs counting sort once per digit.
Comparison sort (built-in sort)O(n log n)O(n)Values are arbitrary numbers, strings, or objects, or the range is far bigger than the list.

Extra memory: O(n + k): counts has k slots and result has n items. The stable version for records also needs an O(n) output array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Counting sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Counting sort O(n + k)
  • Radix sort O(d × n)
  • Comparison sort (built-in sort) O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Counting sort202,0002 million
Radix sort1001 million1 trillion
Comparison sort (built-in sort)339,96620 million

Inputs that need care

5 tricky inputs
An empty list with maxValue = 3
The counting loop does nothing, the writing loop checks 4 empty slots, and the result is [].
A value bigger than maxValue: [2, 6, 1] with maxValue = 4
counts[6]++ writes outside the slots the write loop visits, so 6 is silently dropped and the result is [1, 2]. Compute maxValue with Math.max(...items) if you aren't sure.
Negative values: [3, -1, 2]
counts[-1] is not an array slot, so -1 is dropped too. Shift every value by the minimum (value - min) before counting and add it back when writing.
Decimals: [2, 2.5, 1]
2.5 isn't an index, so it disappears. Counting sort only works on whole numbers, or on keys you can map to whole numbers.
Records, like tasks with a priority from 0 to 3
Writing out bare values loses the rest of each record. Use the stable placement version: turn counts into starting positions and copy each record to its slot.

Variations and follow-ups

Twists interviewers add

Stable counting sort with prefix sums

Turn counts into running totals so that each slot says where its value's first item goes. Then copy each item, in input order, to its position and move that position forward by one. Equal keys keep their order, which is exactly what radix sort needs for each digit.

Counting with an offset

For values from min to max, use max - min + 1 slots and index them with value - min. Temperatures from -20 to 45 need just 66 slots. It is the fix for negative numbers.

Counting letters

To sort the letters of a word, or check whether two words use the same letters, count into 26 slots, one per letter from a to z. It runs in O(n) for any word length.

Hash map counting

When the possible values are few but spread out, like [1000, 5, 1000, 7], count in a Map instead of an array, then sort only the distinct keys. That is O(n + d log d) for d distinct values.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the range: "values are between 0 and 100", "lowercase letters only", "ages", "scores". A small, known range is the signal that you can beat O(n log n).
  • Explain it as "use the value as an index". Say clearly that it is O(n + k), and that it is only better than O(n log n) when k is small compared to n log n.
  • Test by hand with a value missing from the range, a value repeated, and the value maxValue itself, to check the + 1 in the array size.
  • The usual follow-up is "how would you sort records, not just numbers, and keep it stable?". Answer with prefix sums: compute where each key starts, then place the records in input order.

Where frontend code uses it

The same idea in real UI code
  • Sorting reviews by star rating, or tasks by a priority from 0 to 4, needs only a handful of counters.
  • Histograms in dashboards are the counting step on its own: counts per bucket, drawn as bars.
  • Grouping items into a few fixed lanes, such as a kanban board's columns, is the stable counting placement: each item goes into its lane, in its original order.

Related algorithms