Gravity Sort vs Counting Sort
Same 110 values, same shuffle, same speed. Counting Sort finishes first and turns gold: 330 operations to 3,883.
The numbers
- Gravity operations
- 3,883
- Counting operations
- 330
- Gravity average
- S
- Counting average
- n + k
- Gravity worst
- S
- Counting worst
- n + k
Gravity Sort
Gravity Sort (bead sort) drops beads on rods like an abacus, so each row settles to its sorted length. More on Gravity Sort.
Counting Sort
Counting Sort counts how many times each value occurs, then writes the values back in order. More on Counting Sort.
FAQ
Which is faster, Gravity Sort or Counting Sort?
On this shuffle of 110 values, Counting Sort needed 330 operations and Gravity Sort needed 3,883, about 11.8× as many. On average Gravity Sort is S and Counting Sort is n + k.
Which one is stable?
Counting Sort is stable; Gravity Sort is not.
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.