Counting Sort
Count occurrences of each key, prefix-sum the counts, place each element at its final index.
Decision · step 10 of 17Counting and Radix Sort: Counting sort, repeated keys
in[6] = 1, key 1. count[1] drops to 0, and that is its slot: out[0] = 1.
What you will see
A count row fills; prefix sums turn counts into positions; elements drop into place from right to left.
Cost
| Best | O(n + k) |
|---|---|
| Average | O(n + k) |
| Worst | O(n + k) |
| Space | O(n + k) |
k is the key range.
Properties
- × comparison based
- ✓ stable
- × in place
- × adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.