Radix sort on 7 numbers up to two digits. Each pass is a stable counting sort by one digit, ones first, then tens. Stability is what makes it work: after the tens pass, numbers with the same tens digit are still in ones order from the pass before.
Radix sort with 2 passes.
in[0] = 53, ones digit 3: count[3] becomes 1.
Tally 53, count of 3 is 1.
in[1] = 89, ones digit 9: count[9] becomes 1.
Tally 89, count of 9 is 1.
in[2] = 15, ones digit 5: count[5] becomes 1.
Tally 15, count of 5 is 1.
in[3] = 27, ones digit 7: count[7] becomes 1.
Tally 27, count of 7 is 1.
in[4] = 18, ones digit 8: count[8] becomes 1.
Tally 18, count of 8 is 1.
in[5] = 45, ones digit 5: count[5] becomes 2.
Tally 45, count of 5 is 2.
in[6] = 25, ones digit 5: count[5] becomes 3. Every element has been tallied without a single comparison.
Tally 25, count of 5 is 3.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with ones digit at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 0, 0, 1, 1, 4, 4, 5, 6, 7.
in[6] = 25, ones digit 5. count[5] drops to 3, and that is its slot: out[3] = 25.
Place 25 at output index 3.
in[5] = 45, ones digit 5. count[5] drops to 2, and that is its slot: out[2] = 45. A later element with the same ones digit already sits to its right, so going backwards keeps them in input order: stable.
Place 45 at output index 2.
in[4] = 18, ones digit 8. count[8] drops to 5, and that is its slot: out[5] = 18.
Place 18 at output index 5.
in[3] = 27, ones digit 7. count[7] drops to 4, and that is its slot: out[4] = 27.
Place 27 at output index 4.
in[2] = 15, ones digit 5. count[5] drops to 1, and that is its slot: out[1] = 15. A later element with the same ones digit already sits to its right, so going backwards keeps them in input order: stable.
Place 15 at output index 1.
in[1] = 89, ones digit 9. count[9] drops to 6, and that is its slot: out[6] = 89.
Place 89 at output index 6.
in[0] = 53, ones digit 3. count[3] drops to 0, and that is its slot: out[0] = 53.
Place 53 at output index 0.
Pass 2: the output of the ones pass becomes the input, 53, 15, 45, 25, 27, 18, 89, and the counts reset. Now sort by the tens digit.
Second pass by the tens digit.
in[0] = 53, tens digit 5: count[5] becomes 1.
Tally 53, count of 5 is 1.
in[1] = 15, tens digit 1: count[1] becomes 1.
Tally 15, count of 1 is 1.
in[2] = 45, tens digit 4: count[4] becomes 1.
Tally 45, count of 4 is 1.
in[3] = 25, tens digit 2: count[2] becomes 1.
Tally 25, count of 2 is 1.
in[4] = 27, tens digit 2: count[2] becomes 2.
Tally 27, count of 2 is 2.
in[5] = 18, tens digit 1: count[1] becomes 2.
Tally 18, count of 1 is 2.
in[6] = 89, tens digit 8: count[8] becomes 1. Every element has been tallied without a single comparison.
Tally 89, count of 8 is 1.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with tens digit at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 2, 4, 4, 5, 6, 6, 6, 7, 7.
in[6] = 89, tens digit 8. count[8] drops to 6, and that is its slot: out[6] = 89.
Place 89 at output index 6.
in[5] = 18, tens digit 1. count[1] drops to 1, and that is its slot: out[1] = 18.
Place 18 at output index 1.
in[4] = 27, tens digit 2. count[2] drops to 3, and that is its slot: out[3] = 27.
Place 27 at output index 3.
in[3] = 25, tens digit 2. count[2] drops to 2, and that is its slot: out[2] = 25. A later element with the same tens digit already sits to its right, so going backwards keeps them in input order: stable.
Place 25 at output index 2.
in[2] = 45, tens digit 4. count[4] drops to 4, and that is its slot: out[4] = 45.
Place 45 at output index 4.
in[1] = 15, tens digit 1. count[1] drops to 0, and that is its slot: out[0] = 15. A later element with the same tens digit already sits to its right, so going backwards keeps them in input order: stable.
Place 15 at output index 0.
in[0] = 53, tens digit 5. count[5] drops to 5, and that is its slot: out[5] = 53.
Place 53 at output index 5.
Sorted: 15, 18, 25, 27, 45, 53, 89. 2 passes of O(n + 10) each, so O(d x (n + k)) for d-digit numbers, still linear for a fixed number of digits.
Sorted output 15, 18, 25, 27, 45, 53, 89.