Counting Sort

Non-comparison sort in O(n + k) time. Tally values, prefix-sum to positions, scatter right-to-left for stability.

Best: O(n + k) Worst: O(n + k) Space: O(n + k) Stable 0 Comparisons
slow fast
Scanning
Incremented/Placed
Prefix Sum
Placing
Stability Tie
Step
0/0
Phase
-
Comparisons
0
Reads
0
Writes
0

Algorithm Trace

Press Start to run animation, or Step to advance one step at a time.

Counting Sort. Works only on small bounded integer keys (k = O(n)). The right-to-left placement in Phase 3 is required for stability — equal keys keep their input order. This stability is what makes Counting Sort a usable inner pass for Radix Sort. No element is ever compared to another; values are used directly as array indices.