Сортировка подсчетом

Пусть у нас есть массив source из n десятичных цифр (m = 10).
Например, source[7] = { 7, 9, 8, 5, 4, 7, 7 }, n=7. Здесь положим const k=1.

1. Создать массив count из m элементов(счетчиков).

2. Присвоить count[i] количество элементов source, равных i. Для этого:

a. проинициализовать count[] нулями,

b. пройти по source от начала до конца, для каждого числа увеличивая элемент count с соответствующим номером.

В нашем примере count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }

3. Присвоить count[i] значение, равное сумме всех элементов до данного:
count[i] = count[0]+count[1]+...count[i-1].
В нашем примере count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }
Эта сумма является количеством чисел исходного массива, меньших i.

4. Произвести окончательную расстановку.

Для каждого числа source[i] мы знаем, сколько чисел меньше него - это значение хранится в count[ source[i] ]. Таким образом, нам известно окончательное место числа в упорядоченном массиве: если есть K чисел меньше данного, то оно должно стоять на позиции K+1.
Осуществляем проход по массиву source слева направо, одновременно заполняя выходной массив dest:

Таким образом, число c=source[i] ставится на место count[c]. На этот случай, если числа повторяются в массиве, предусмотрен оператор count[c]++, который увеличивает значение позиции для следующего числа c, если таковое будет.

Циклы занимают (n + m) времени. Столько же требуется памяти.

Итак, мы научились за (n + m) сортировать цифры. А от цифр до строк и чисел - 1 шаг. Пусть у нас в каждом ключе k цифр (m = 10). Аналогично случаю со списками отсортируем их в несколько проходов от младшего разряда к старшему.

Общее количество операций, таким образом, (k(n+m)), при используемой дополнительно памяти (n+m). Эта схема допускает небольшую оптимизацию. Заметим, что сортировка по каждому байту состоит из 2 проходов по всему массиву: на первом шаге и на четвертом. Однако, можно создать сразу все массивы count[] (по одному на каждую позицию) за один проход. Неважно, как расположены числа - счетчики не меняются, поэтому это изменение корректно.
Таким образом, первый шаг будет выполняться один раз за всю сортировку, а значит, общее количество проходов изменится с 2k на k+1.