Counting sort

O(n + k)

Counting sort is a non-comparison sort for integers drawn from a small range. It makes one pass to count how many times each value appears, then walks the counts from smallest to largest, writing each value out the right number of times. There are no comparisons or swaps, so it runs in O(n + k) where k is the size of the value range — beating the O(n log n) comparison-sort barrier when k is not much larger than n. The trade-off is space and the range restriction: it's ideal for things like ages, scores, or bytes, and is the stable building block inside radix sort.

Array
Edit the input and press Play

How it works

  1. Find the value range and make a tally slot for each value.
  2. Scan the array, counting how many times each value occurs.
  3. Walk the tallies from low to high, emitting each value that many times.
  4. The rebuilt array is sorted — no comparisons were ever made.

Pseudocode

1countingSort(a):                    # O(n + k)2  k ← max(a) − min(a) + 13  count ← array of k zeros4  for v in a: count[v − min]++       # tally each value5  out ← []6  for v from 0 to k-1:7    append (v + min) count[v] times   # emit in order8  return out