1. Count occurrences
Create C[0…30], initially filled with zeros. After reading the students, the only nonzero cells are C[18]=2, C[24]=2, C[27]=1 and C[30]=1.
Sorting algorithms · 5/7
Counting sort
Replaces comparisons with counts of integer keys.
Average timeΘ(n + k)
SpaceΘ(n + k)
StableYes
In placeNo
How it works
Count how often each value occurs. After cumulative sums, C[v] tells how many elements are ≤ v, so the next occurrence of v belongs at C[v]−1. Scanning the input from right to left and decreasing the counter produces stable output.
Invariant: After accumulation C[v] counts items ≤ v; while building the output, C[v]−1 is the rightmost free position reserved for v.
Example: students sorted by grade
Suppose we want to sort the students in a course using their grade as the key, which can only be an integer from 0 to 30. The range contains just 31 possible values: instead of comparing students in pairs, Counting sort can reserve one counter for each grade.
Initial list: Anna 24, Luca 18, Sara 27, Paolo 24, Giulia 30, Marco 18.
2. Compute cumulative counts
Add each cell to the previous one. Now C[18]=2, C[24]=4, C[27]=5 and C[30]=6: for example, four students have a grade ≤24, and the last position reserved for a 24 is C[24]−1=3.
3. Build the output
Scan the list from right to left. Each student with grade v goes into B[C[v]−1], then C[v] is decreased. The result is: Luca 18, Marco 18, Anna 24, Paolo 24, Sara 27, Giulia 30.
Why scan from the right? This preserves the initial order of students with equal grades: Luca remains before Marco and Anna before Paolo. This is exactly what makes Counting sort stable. With only 31 counters, the cost is Θ(n+31), so it is essentially linear in the number of students.
Step-by-step visualization
Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.
Use 2 to 16 values from 0 to 999, spanning a range no wider than 80.
- Comparisons
- 0
- Writes
- 0
- Swaps
- 0
- Pass / level
- 0
active
comparison
pivot / key
final
Pseudocode linked to the visualization
C[0 … k] ← 0for value in A: C[value]++for i ← 1 to k: C[i] ← C[i] + C[i − 1]for i ← n − 1 downto 0B[C[A[i]] − 1] ← A[i]C[A[i]]--copy B into A
The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.
Complexity analysis
Reading n items and initializing k counters is necessary: Θ(n+k).
Input order does not change the passes: Θ(n+k).
Worst case performs the same linear passes.
Θ(k) counters and Θ(n) stable output: Θ(n+k), not in place.
Properties at a glance
Stability concerns the relative order of elements with equal keys.
This classification refers to the version shown on this page.
When to use it and what to avoid
A good choice when…
Excellent for integers whose range k is not much larger than n.
Common mistake
A huge max−min range wastes time and memory. This visualizer accepts nonnegative integers.