How counting sort works
- Find the largest value.
GetMaxVal()does that in one walk through the array. - Create an array of counters with one slot for every value from 0 to the largest.
- Walk through the input and add 1 to the counter of each value.
- Walk through the counters from 0 upwards. Write each value into the array as many times as it was counted.
What the colours mean
The occurrences row under the bars holds the counters. The small number under each cell is the value it counts. Yellow marks what is being read and pink what is being written. While the result is written back, bars that still hold old input are faded.
Counting Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n + k) | O(n + k) | O(n + k) | O(k) | In its stable form |
The work depends on two numbers: the n values to count and the k + 1 counters to walk through, where k is the largest value. Counting sort is fast when the values sit in a small range and wasteful when one value is far above the rest. Type 1, 2, 30 into the box: three values need 31 counters.
The comparison counter shows only the n - 1 comparisons GetMaxVal() makes. No two values are ever compared to decide their order. This method takes whole numbers from 0 up, and the visualizer stops at 30 so that the counters fit on the screen.
The C# code
The listing beside the bars is the GetMaxVal() and CountingSort() methods from Counting Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is counting sort stable?
This version writes fresh numbers from the counters, so there is nothing to keep in order. To sort records by a key and keep ties in their original order, use running totals and fill the output from the right. The article shows that as StableCountingSort().
Can counting sort handle negative numbers?
Not as written, because a negative value would be a negative array index. Subtract the smallest value from every key first, so that the smallest maps to counter 0.
When is counting sort faster than quicksort?
When the range of values is small compared with the number of values, for example a million ages or exam scores. Its time grows with n + k, where k is the largest value.