Counting Sort vs Radix Sort
Same 220 values, same shuffle, same speed. Counting Sort finishes first and turns gold: 660 operations to 1,980.
The numbers
- Counting operations
- 660
- Radix operations
- 1,980
- Counting average
- n + k
- Radix average
- n·k
- Counting worst
- n + k
- Radix worst
- n·k
Counting Sort
Counting Sort counts how many times each value occurs, then writes the values back in order. More on Counting Sort.
Radix Sort
Radix Sort sorts numbers digit by digit, from the least significant digit up, without comparing values. More on Radix Sort.
FAQ
Which is faster, Counting Sort or Radix Sort?
On this shuffle of 220 values, Counting Sort needed 660 operations and Radix Sort needed 1,980, about 3.0× as many. On average Counting Sort is n + k and Radix Sort is n·k.
Which one is stable?
Both are stable.
How is the race fair?
Both algorithms start from the same shuffle and run the same number of operations per frame. Every comparison, swap and write counts as one operation, so the one that needs fewer operations finishes first.