vizlearn
Home / Algorithms

Counting Sort

Algorithms & Data StructuresBy Updated

A non-comparison sorting algorithm that counts the occurrences of distinct key values to reconstruct a sorted array.

Parameters

15
9

Visualization

Step: 0
1. Main Array
2. Frequency Count Array (Size: K + 1)
Click Step or Auto-Run to begin counting sort.

Algorithm Insight

Counting Sort is a Non-Comparison sorting algorithm, great when the range of inputs ($K$) is small compared to the array size ($N$).

  • 1. Initialize a Count Array of size $K+1$ with zeros.
  • 2. Iterate the main array. Increment Count[value] for each element read.
  • 3. Iterate the Count Array. Overwrite the main array sequentially with valid elements.

Efficiency

Time Complexity O(N + K)
Space Complexity O(K)

Overview

Every comparison-based sort needs Ω(n log n) comparisons in the worst case; that is a proven lower bound, not an engineering limit. Counting sort is faster because it never compares two elements. Instead it uses each value as an index, which is a fundamentally different source of information.

Beating the comparison lower bound

The requirement is that values are integers in a known, bounded range.

The three passes

Sort [3, 1, 4, 1, 5, 3, 1] with values in 0–5.

1. Count. Walk the input, incrementing count[value]:

index: 0 1 2 3 4 5
count: 0 3 0 2 1 1

2. Prefix sum. Replace each entry with the running total, so each slot holds the number of elements less than or equal to that value:

count: 0 3 3 5 6 7

3. Place. Walk the input backwards, and for each element use count[value] − 1 as its output index, then decrement. The result is [1, 1, 1, 3, 3, 4, 5].

Three linear passes and no comparison anywhere.

The complexity, and the k that matters

Counting sort runs in O(n + k) time and O(n + k) space, where n is the number of elements and k is the size of the value range.

When k is O(n) this is linear and beats every comparison sort. When k is large it collapses: sorting 1,000 integers spread over the full 32-bit range means allocating a counting array of 4 billion entries to sort 1,000 values. The algorithm is not slow there so much as unusable.

So the honest rule is that counting sort is linear in n and k together, and it is only a good idea when k is comparable to n or smaller.

Exploration guide

  1. Watch the tally build. Set Array Size to 20 and Max Value Limit (K) to 5, then press Next Step through the counting pass. No two input elements are ever compared — each one simply increments a bucket.
  2. Make k small and see it win. Keep Array Size at 25 and set Max Value Limit (K) to 3. The counting array is tiny, buckets fill fast, and the whole sort finishes in three quick sweeps.

Common mistakes with Counting Sort

  • Assuming values start at zero. With a range like 1000–1005, allocating 1006 buckets wastes almost all of them. Offset by the minimum: index with value − min and allocate max − min + 1.
  • Walking forwards in the placement pass. Silently destroys stability, and therefore silently breaks any radix sort built on top.
  • Using it on floats or strings. The value must be usable as an array index. Floats and arbitrary strings need a different approach — bucket sort or radix sort on their byte representation.
  • Ignoring k in the complexity. Calling counting sort “O(n)” without qualification is the most common mistake in exams and interviews. It is O(n + k), and k is what decides whether it is usable.

Radix sort: counting sort applied digit by digit

Counting sort fails on large ranges. Radix sort fixes that by sorting on one digit at a time, using counting sort for each pass.

Sorting 32-bit integers: instead of a range of 4 billion, do four passes over bytes, each with a range of 256.

O(d × (n + k))  where d = number of digits, k = base

For 32-bit integers in base 256: d = 4, k = 256, so O(4(n + 256)) — effectively linear.

The important requirement is that each pass must be stable, or earlier digits' ordering is destroyed. That is exactly why the stable version of counting sort matters, and why the two topics belong together.

Least significant digit first is the usual direction: sort by the last digit, then the next, and so on. After the final pass the array is fully sorted, because each pass preserves the previous ones' work.

Radix sort is genuinely used: for fixed-width integer keys at scale it outperforms comparison sorts, and it appears in database sorting, GPU sorting libraries and some string sorting.

Sources and next steps

Run it in Python

No comparison between two elements appears anywhere in this program. It sorts by counting, which is how it beats the O(n log n) bound — and the last block shows what that costs when the value range is large.

counting_sort.pyPython 3
Output
How the code works
  1. counts[value - lo] += 1The value itself is the index. That is the trick, and it is also the restriction: this only works for keys that can be used as array offsets.
  2. for i in range(1, k): counts[i] += counts[i - 1]Turns counts into positions. After this, counts[v] is the number of items less than or equal to v — which is exactly where the last v belongs in the output.
  3. for value in reversed(a):Walking backwards, combined with decrementing before writing, keeps equal items in their original order. Iterate forwards and the sort still works but is no longer stable — which would break radix sort, its main customer.
  4. out[counts[value - lo]] = valueEach item is placed directly at its final index. No item is ever compared with another, so the O(n log n) lower bound for comparison sorts simply does not apply.
  5. k = hi - lo + 1The whole cost story. O(n + k) is linear when k is comparable to n, and a disaster when it is not — as the three-item example shows.
Change one thing
  • Sort exam marks: [random.randint(0, 100) for _ in range(50)]. Fifty items, 101 counters — this is the shape counting sort is for.
  • Iterate forwards instead of reversed(a), and sort (value, tag) pairs by value. Watch the tags come out in the wrong order.
  • Remove the - lo offset and sort a list with negative numbers. The IndexError is why the offset is there.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: Watch the tally build. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. How does counting sort beat the O(n log n) lower bound?
  2. Why does the final loop iterate over reversed(a)?
  3. The program sorts [5, 100000, 3]. What is the problem?





 Cheat sheet
Counting Sort
Sort integers without a single comparison by tallying how often each value occurs, then rebuilding the array in order.
ALGORITHMS · vizlearn.in/dsa/counting_sort.html
More in Algorithms
AlgorithmsRadix SortAlgorithmsStacks (LIFO)AlgorithmsQueues (FIFO)AlgorithmsLinked Lists
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact