AlgoVerse

Counting sort

No comparisons: count how often each value occurs and compute each item's place in the output directly from prefix sums.

Comparison sorts cannot beat n log n. Counting sort does not compare at all: when the items are small integers in 0..k, it uses the value itself as an index.

Read the full explanation ↓
Input:
n=8PDF export

Eight numbers from 0 to 5 with repeats; the count array has six cells.

  1. def counting_sort(a):
  2. k = max(a)
  3. count = [0] * (k + 1)
  4. for x in a:
  5. count[x] = count[x] + 1
  6. for v in range(1, k + 1):
  7. count[v] = count[v] + count[v - 1]
  8. out = [0] * len(a)
  9. for j in range(len(a) - 1, -1, -1):
  10. count[a[j]] = count[a[j]] - 1
  11. out[count[a[j]]] = a[j]
  12. return out

Invariant: After the prefix-sum phase, count[v] is the number of items ≤ v: one past the last place of v in the output.

Start

2051320324350637

Local variables

Orange = changed in this step

a list

25302303

Call stack

  1. counting_sort()line 1
Step 1 of 58
Black = init, place · Orange = key stepinit: 0/1 · count: 0/8 · prefix: 0/5 · place: 0/8

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • count
    • prefix
    • place
    • current input (n=8)
    0510152046810121416n = number of itemscountplaceprefix
    Show as a table
    ncountprefixplace
    447.44
    668.36
    888.28
    10108.310
    12128.812
    14148.814
    16168.816
    Explanation

    The idea

    Comparison sorts cannot beat n log n. Counting sort does not compare at all: when the items are small integers in 0..k, it uses the value itself as an index.

    1. Count: count[x] is how many times x occurs.
    2. Prefix sums: after count[v] += count[v − 1], count[v] is the number of items ≤ v; so the last item with value v belongs at position count[v] − 1 of the output.
    3. Place: from the end of the array to the start, write each item to its place in the output and decrease its count.

    Cost

    O(n + k) time and memory. When k is small compared with n, it beats every comparison sort; when k is large (the "wide range" input), the count array drives the cost up.

    Stability

    Because the last phase starts from the end, the later of two equal items lands in the later position: the sort is stable. Radix sort needs exactly this property.

    What to watch in the trace

    • The count and out arrays are in the memory panel; the bars are the input a, and the j arrow marks the item being placed.
    • Look at the counters: there is no compare at all.