Counting sort on 7 keys from 0 to 9. No element is ever compared with another: the cnt row tallies each key, the tallies become running totals, and every element is then written straight to its final place in out.
Counting sort of 7 values.
in[0] = 4, key 4: count[4] becomes 1.
Tally 4, count of 4 is 1.
in[1] = 2, key 2: count[2] becomes 1.
Tally 2, count of 2 is 1.
in[2] = 2, key 2: count[2] becomes 2.
Tally 2, count of 2 is 2.
in[3] = 8, key 8: count[8] becomes 1.
Tally 8, count of 8 is 1.
in[4] = 3, key 3: count[3] becomes 1.
Tally 3, count of 3 is 1.
in[5] = 3, key 3: count[3] becomes 2.
Tally 3, count of 3 is 2.
in[6] = 1, key 1: count[1] becomes 1. Every element has been tallied without a single comparison.
Tally 1, count of 1 is 1.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with key at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 1, 3, 5, 6, 6, 6, 6, 7, 7.
in[6] = 1, key 1. count[1] drops to 0, and that is its slot: out[0] = 1.
Place 1 at output index 0.
in[5] = 3, key 3. count[3] drops to 4, and that is its slot: out[4] = 3.
Place 3 at output index 4.
in[4] = 3, key 3. count[3] drops to 3, and that is its slot: out[3] = 3. A later element with the same key already sits to its right, so going backwards keeps them in input order: stable.
Place 3 at output index 3.
in[3] = 8, key 8. count[8] drops to 6, and that is its slot: out[6] = 8.
Place 8 at output index 6.
in[2] = 2, key 2. count[2] drops to 2, and that is its slot: out[2] = 2.
Place 2 at output index 2.
in[1] = 2, key 2. count[2] drops to 1, and that is its slot: out[1] = 2. A later element with the same key already sits to its right, so going backwards keeps them in input order: stable.
Place 2 at output index 1.
in[0] = 4, key 4. count[4] drops to 5, and that is its slot: out[5] = 4.
Place 4 at output index 5.
Sorted: 1, 2, 2, 3, 3, 4, 8. Two passes over n elements and one over k = 10 keys: O(n + k), below the comparison bound of n log n, at the price of needing small integer keys.
Sorted output 1, 2, 2, 3, 3, 4, 8.