How It Works
Sort Target
Algorithm
Speed
Normal ~12s · 240 ms/step
Counting sort(1954)
▶ Try this Source
O(n+k) ✓ Stable ✗ In-place ✗ Adaptive
🔧 How it works

Counts how many times each distinct value appears, computes a running prefix-sum of those counts to determine each value's output position, then writes every element directly to its computed position.

🎯 Key property

Never compares values against each other, positions are computed arithmetically from counts, which is why it breaks the O(n log n) comparison-based lower bound and runs in O(n + k) where k is the value range.

👁 Watch for
  • IndexRead each element is read to increment its slot in the frequency table; no element moves during this phase
  • IndexWrite the prefix-sum pass overwrites the frequency table with cumulative output positions; each element is then written to the output buffer in a single placement pass
  • End of phase three distinct phases are clearly visible, count, prefix-sum, and place, none of which involves any comparisons
🕰 History 🌳 Lineage ⚡ Optimization
Initial State
This is the array before sorting. Follow Counting sort step by step.
Main Array
5
0
3
1
8
2
1
3
9
4
2
5
7
6
4
7
BucketsScatter
1
2
3
4
5
6
7
8
9
0 / 50 ops ( 0.0%) 0.0%
Sorting is
a spectacle.
Algorithms at work, in a daily vertical feed. Watch, play, challenge — and go deeper when you're ready.
Loading 0%
An unhandled error has occurred. Reload 🗙