Counting sort does not compare values at all. It counts how many times each value appears, turns those counts into running totals (prefix sums) that tell where each value’s group ends, and then places every value straight into its final position in an output array. This visualizer shows the count array and the output array under the bars and highlights the cell being updated at each step.
It runs in O(n + k) time, where k is the range of values, so it beats every comparison sort when the values are small whole numbers such as ages, grades or digits. Values here range from 0 to 15 so the count array fits on the screen; type your own numbers up to 50 to try a wider range.
How to use the Counting Sort Visualizer tool
- Pick an array size and an input: random, nearly sorted, reversed or few unique values. You can also type your own numbers.
- Press Play to watch the sort, or Step to move one comparison or swap at a time. Back goes one step back.
- Follow the colours: orange bars are being compared, red bars are being swapped or written, green bars are in their final place.
- Read the message under the controls and the highlighted pseudocode line to see exactly what the algorithm is doing.
- Change the speed, switch the code tab to C++, Java, Python or JavaScript, and compare the counters with other inputs.
Why use ToolOrca Counting Sort Visualizer
- Animated bars with play, pause, step and step back
- Speed slider and a position slider to jump to any step
- Count array and output array shown step by step
- Random, nearly sorted, reversed and few-unique inputs, or your own numbers
- Highlighted pseudocode line for every step
- Code in C++, Java, Python and JavaScript
- Works on phones and tablets, keyboard accessible
How counting sort works
1. Count: make an array count of size max + 1 filled with zeros and add 1 to count[x] for every value x. 2. Prefix sums: for v from 1 to max, add count[v − 1] to count[v]. Now count[v] is the number of values ≤ v, which is one past the last position where v belongs. 3. Place: go through the input from right to left; for each x, decrease count[x] and write x at output[count[x]]. 4. Copy the output back.
Going from right to left in step 3 keeps equal values in their original order, which makes counting sort stable. That stability is what lets radix sort use it digit by digit.
Time and space complexity of counting sort
Counting takes O(n), the prefix sums O(k) and the placement O(n), so the total is O(n + k) time and O(n + k) extra space, where k is the largest value. When k is about the same size as n or smaller, that is linear time, faster than the O(n log n) lower bound for comparison sorts, which does not apply because nothing is compared.
When to use counting sort
Use counting sort for whole numbers (or keys that map to them) in a small range: exam scores 0 to 100, ages, letters, or the digits inside radix sort. Do not use it when the range is huge compared with the number of values, for example sorting 10 numbers up to a billion, because the count array would be enormous.
Every visualizer on this site runs in your browser with the same controls: Play, Pause, Step forward, Step back and a speed slider. You can also drag the position slider to jump to any step, or focus the drawing and use the Space bar and arrow keys.
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 range of values (the largest value plus one).
Why can counting sort beat O(n log n)?
The O(n log n) limit only applies to sorts that work by comparing values. Counting sort uses the values as array indexes instead.
Can counting sort handle negative numbers?
Yes, by shifting: subtract the minimum value from every key so the smallest becomes 0, then add it back when writing the output.
Is counting sort stable?
Yes, when the placement step goes through the input from right to left, as shown here.