Counting sort
Counting sort counts how many times each distinct value appears in the array, then walks through the possible values from smallest to largest, writing each one back into the array as many times as it was counted. It never compares two values against each other, only against a stored count.
When it is the right choice
Counting sort is an excellent choice when the values are integers drawn from a range k that is small relative to n, such as exam scores out of 100 or ages in years — its O(n + k) time beats any comparison sort's O(n log n) once k is small enough. It is a poor choice when the range k is large or unbounded, since its extra space and time both scale with k as well as n; sorting a million distinct sixteen-digit account numbers this way would need a count array with quadrillions of cells.
How it works
- Count how many times each value from the smallest to the largest appears in the array.
- Read each value in turn and increase its count by one.
- Once every value has been counted, walk through the possible values from smallest to largest.
- For each value, while it still has a remaining count, write it into the next position of the array and reduce its count by one.
Worth noticing
- Its comparisons counter stays at zero for the entire run — that is the point. Counting sort never asks whether one value is greater than another, which is also why the usual n log n lower bound for comparison sorts does not apply to it.
- Its cost depends on the value range k as well as n, shown here as the counts track beneath the array: a wide range of values needs a correspondingly wide counts track, which is why this tool restricts it to a range it can still display.
- The version implemented here is not stable, because it forgets which original element each count came from; a stable version exists but needs a second output array the same size as the input.
Cost
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
- O(n + k)
- Extra space
- O(n + k)
- Stable
- No