Sorting Tested code in 3 languages

Counting Sort, Visualized Step by Step

Count how many times each value appears, turn the counts into positions, then drop every value straight into its slot. No two values are ever compared to decide the order. Press play to watch the count array and the output fill up next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive counting sort

The smallest value is 1 and the largest is 6, so make 6 counters, one for each value from 1 to 6, all starting at 0.

0Counter updates
0Writes
1/–Step
def counting_sort(a):    if not a:        return    low, high = min(a), max(a)    count = [0] * (high - low + 1)    for v in a:        count[v - low] += 1    for d in range(1, len(count)):        count[d] += count[d - 1]    out = [0] * len(a)    for i in range(len(a) - 1, -1, -1):        d = a[i] - low        count[d] -= 1        out[count[d]] = a[i]    for i in range(len(a)):        a[i] = out[i]

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How counting sort works

Every sort you have seen so far decides the order by comparing two values. Counting sort never does. It uses each value as an index into an array of counters. Think of sorting a stack of exam papers by grade: you do not compare papers with each other, you drop each one into the tray for its grade and then stack the trays in order.

Count. Find the smallest and largest value, low and high, and make one counter for every value in between: k = high − low + 1 counters. Walk the array once and add 1 to the counter of each value. Subtracting low is what lets negative numbers work: the value low uses counter 0.

Running totals. Add each counter to the one after it. Now the counter for value v holds how many values are ≤ v, which is exactly one past the last position v will occupy in the sorted output. In the CLRS example below, the counter for 3 becomes 7, so the three 3s end at index 6.

Place, from the right. Walk the input from its last element to its first. For each value, take one off its counter and write the value to that index of out. Walking right to left means the last of several equal values gets the last slot, so equal values keep their original order. That property, stability, is why counting sort can be the digit pass inside radix sort. Finally, copy out back.

The algorithm in 5 steps

  1. 1 Find low and high and make high − low + 1 counters, all 0.
  2. 2 For each value v, add 1 to count[v − low].
  3. 3 Running totals: for d from 1 up, count[d] += count[d − 1]. Now count[d] is the number of values ≤ low + d.
  4. 4 Walk the input from right to left: take 1 off the value's counter and write the value to out at that index.
  5. 5 Copy out back into the array.

Worked example

This is the array from Figure 8.2 of CLRS (Introduction to Algorithms), run through the same code as the visualizer. The first row is the count array after counting, the second after the running totals. Each row after that places one value into out, walking the input from the right. The final copy back into the array is counted in the total but not listed.

Input: [2, 5, 3, 0, 2, 3, 0, 3]

  1. Step 9 Read 3 (index 7): the counter for 3 goes up to 3. count 200122330415
  2. Step 14 The counter for 5 becomes 8: 8 values are ≤ 5. Each counter now says where the last copy of its value ends in the sorted output. count 202142737485
  3. Step 16 Write 3 to out[6]. out ······3·
  4. Step 18 Write 0 to out[1]. out ·0····3·
  5. Step 20 Write 3 to out[5]. out ·0···33·
  6. Step 22 Write 2 to out[3]. out ·0·2·33·
  7. Step 24 Write 0 to out[0]. out 00·2·33·
  8. Step 26 Write 3 to out[4]. out 00·2333·
  9. Step 28 Write 5 to out[7]. out 00·23335
  10. Step 30 Write 2 to out[2]. Every value is placed: out is sorted. out 00223335

Total for this run: 21 counter updates and 16 writes, in 39 animation steps. Result: 0, 0, 2, 2, 3, 3, 3, 5.

Time and space complexity

Best

O(n + k)

There is no best case: it makes the same fixed passes over the n values and the k counters, whatever the order of the input. k is the number of possible values, high − low + 1.

Average

O(n + k)

The same fixed passes. When k is no bigger than a constant times n, that is O(n): linear time.

Worst

O(n + k)

Still linear in n, but k can dominate: two values, 0 and 1,000,000, need a million counters to sort two numbers.

Space

O(n + k)

The count array (k entries) plus the output array (n entries). It does not sort in place.

Stable:
Yes
In place:
No
Comparison sort:
No
Works on:
Integer keys in a small range

Same 8 numbers, comparison sorts vs counting sort

Every comparison sort needs at least ⌈log₂(n!)⌉ comparisons in the worst case, 16 for 8 values, and that grows like n log n. Counting sort never compares two values to order them: on the visualizer's numbers it runs one counting pass, with 21 counter updates and 16 writes. Computed from the code on these pages, not typed in.

AlgorithmComparisonsOther work
Counting sort0 (after finding the smallest and largest)21 counter updates, 16 writes
Merge sort1724 writes
Quick sort399 swaps
Heap sort2416 swaps
Insertion sort1913 shifts

Fewer operations on 8 numbers is not the point; the growth is. Comparison sorts grow like n log n. Counting sort grows like n + k, where k is the number of possible values, so it wins only while k stays small.

When to use it, and when not to

Good fit

  • The keys are integers in a small range: exam scores 0 to 100 (101 counters), ages 0 to 120, star ratings 1 to 5, bytes 0 to 255. Then it beats any comparison sort, because it is O(n) and makes no comparisons.
  • You need the per-digit pass of radix sort. Radix sort runs counting sort once per digit with k = 10 (or k = 256 per byte), and it only works because counting sort is stable.
  • You are sorting records by a small integer key and must keep the original order of equal keys, such as orders by priority 1 to 5 where earlier orders stay first.
  • You need the frequencies anyway. The count array after step 2 is a histogram, which solves "most frequent element" or "is this an anagram" questions in the same pass.

Pick something else when

  • The range is large compared with n. Sorting 1,000 values that lie between 0 and 10⁹ would need a billion counters, about 4 GB as 32-bit ints. Use radix sort or a comparison sort.
  • The keys are not integers: floats, strings or objects compared by a custom rule. They cannot be used as array indices directly. Map them to small integers first, or use a comparison sort.
  • Memory is tight. Counting sort needs O(n + k) extra space; heap sort sorts in place with O(1).
  • The data is tiny or almost sorted. Insertion sort or your language's built-in sort is simpler and just as fast there.

Common mistakes and bugs

  1. 1.Forgetting the offset for negative values

    Without − low, a value of −3 indexes count[−3]. Java throws ArrayIndexOutOfBoundsException, but Python silently reads count[-3] as the third counter from the end, so the program runs and the output is wrong. Always size the array as high − low + 1 and index with v − low.

  2. 2.Placing left to right

    With running totals, each counter points one past the last slot of its value. Walking the input from the left and filling from those positions puts the first of two equal values in the later slot, which reverses equal values. On plain integers you cannot see it; inside radix sort it gives a wrong answer.

  3. 3.Writing before decrementing

    After the running totals, count[d] equals the number of values ≤ that value, which is one past the last index. Writing to out[count[d]] first and decrementing after writes one place too far right, and the last value runs off the end of out. Decrement first, as the code here does.

  4. 4.Rebuilding values from the counts when there is data attached

    The short version, "for each value v, write v count[v] times", is fine for bare integers. It is not a stable sort of records: if you are sorting students by grade, it rebuilds grades and loses which student had which. Use the running-total version, which moves the original items.

  5. 5.Using it on a wide range because it is "O(n)"

    O(n + k) hides k. Sorting ten phone numbers by value would need 10¹⁰ counters. Check that k is no bigger than a small multiple of n before choosing counting sort.

Interview questions

Try answering before you open the model answer.

Q1 Comparison sorts need Ω(n log n) comparisons. How does counting sort run in O(n)?

Model answer: The lower bound only applies to algorithms that learn about the order by comparing pairs of elements: there are n! possible orders, and each yes/no comparison can at best halve them, so log₂(n!) ≈ n log₂ n comparisons are needed. Counting sort uses each value as an array index instead, so the bound does not apply. The price is that keys must be small integers.

Q2 Why does the placing loop walk from right to left?

Model answer: After the running totals, each counter points one past the last slot of its value, and we fill slots from that end backwards. Visiting the input from the right means the last occurrence of a value gets the last slot and earlier occurrences get earlier slots, so equal values keep their order. That stability is what radix sort relies on.

Q3 Sort one million exam scores, each between 0 and 100.

Model answer: Counting sort with 101 counters: one pass to count, 100 additions for the running totals, one pass to place. That is about three million simple steps (count, place, copy back) and 101 extra integers plus the output, versus roughly 20 million comparisons for an O(n log n) sort. If you only need the scores and not who scored them, you can even skip the output array and rewrite from the counts.

Q4 Sort an array that contains only 0s, 1s and 2s.

Model answer: Counting sort works: count the three values, then write that many 0s, 1s and 2s. That is two passes and O(1) extra space. The follow-up is usually "in one pass": Dijkstra's Dutch national flag partition, with three pointers low, mid and high, swaps values into place in a single scan.

Q5 When would you pick radix sort over counting sort?

Model answer: When the range of values is large. Counting sort needs a counter for every possible value, so 32-bit integers would need about 4.3 billion counters. Radix sort runs counting sort on one digit at a time, so each pass needs only 10 counters (or 256 per byte): four byte passes cover any 32-bit integer.

Frequently asked questions

What is the time complexity of counting sort?

O(n + k), where n is the number of values and k is the size of their range, high − low + 1. It is the same for every input order: one pass to count, one over the counters for running totals, one to place. When k is at most a constant times n, that is linear time, O(n).

Is counting sort stable?

Yes, in the running-total version shown here. It walks the input from right to left and fills each value's slots from the back, so equal values come out in their original order. The shortcut version that rewrites values from the counts has no notion of the original items, so it cannot keep records in order.

Can counting sort handle negative numbers?

Yes, by shifting. Find the smallest value, low, and store the count of v at index v − low. The array then needs high − low + 1 counters and the rest of the algorithm is unchanged. The code on this page does exactly that, which is why the visualizer accepts negative numbers.

Why is counting sort not used for everything if it is O(n)?

Because the hidden term k can be huge. Sorting a few numbers spread between 0 and a billion would need a billion counters. It also needs integer keys and O(n + k) extra memory. It shines on small ranges, such as scores, ages, bytes or characters, and as the digit pass inside radix sort.

Is counting sort a comparison sort?

No. It never compares two elements to decide which goes first; each value is used as an index into the count array. That is how it beats the Ω(n log n) lower bound for comparison sorts. The code here only compares while finding the smallest and largest value, a single scan before sorting starts.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Section 8.1, the Ω(n lg n) lower bound for comparison sorts (Theorem 8.1); Section 8.2, Counting sort, Θ(k + n), stable, with the example array of Figure 8.2 used in the worked example.
  2. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., Addison-Wesley, 1998)
    Section 5.2, Algorithm D (distribution counting), the stable count-and-place method.
  3. Wikipedia, "Counting sort"
    History: counting sort and its use in radix sorting were both invented by Harold H. Seward in 1954.

The animation, the worked example and the step counts are all generated by one implementation of counting sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms