Counting Sort

Imagine we are sorting a collection of (small) integers where the range of the values is known.

Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to build the sorted array.

Demo
Analysis

Counting sort has a $O(k+n)$ running time where input contains $n$ integers in the range $[0, k)$.

  • $O(k)$ to create the frequency table (counts array).
  • $O(n)$ to put $n$ values into frequency table.
  • $O(k)$ to reproduce the sorted sequence.

Counting sort is efficient if the range of input data, $k$, is not significantly greater than the number of objects to be sorted, $n$.

If $k \in O(n)$ then counting sort runs in $O(n)$.

Counting sort takes $O(n + k)$ space:

  • $O(n)$ input space
  • $O(k)$ auxiliary space

Note that Counting sort only works when the range of potential items in the input is known ahead of time.

Resources