Distribution sorts · Intermediate
Counting Sort
Count each integer key, turn counts into positions, then place every item directly.
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
- O(n + k)
- Space
- O(n + k)
- Stability
- Stable
- Memory model
- Uses auxiliary storage
How it builds order
- Count how often each key appears.
- Prefix-sum the counts into ending positions.
- Scan input backward and place each item into output.
- Copy output back.
Why it works
Counts determine exactly how many smaller keys exist, which determines every key’s output interval.
Watch for: Its k term is the key range; a huge sparse range makes the count shelf expensive.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.