Counting Sort
- Ω( n + k )
- Θ( n + k )
- O( n + k )
- space O( n + k )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How counting sort works
Counting sort never compares elements to each other to place them. It counts how many times each value occurs, then writes the values back in order using those counts.
Read more
The only comparisons are the n-1 needed to find the largest value, which sets the size of the count table. That is why its comparison count is so small next to the other algorithms: the work happens as reads and writes of the count table, shown in Reads and Writes. It is fast when the range of values is small compared to the number of elements.
| Best time | Ω( n + k ) | good |
|---|---|---|
| Average time | Θ( n + k ) | good |
| Worst time | O( n + k ) | good |
| Worst space | O( n + k ) | fair |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.