Изменения

В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Сам по себе алгоритм представляет собой цикл по количеству разрядов, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-ый разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex>, используется вспомогательный массив <tex> C </tex>. Функция <tex> digit(x, i) </tex> возвращает <tex> i </tex>-ый разряд числа <tex> x </tex>. Так же считаем, что значения разрядов меньше <tex> k </tex>.

for j = 0 to k - 1 // обнуление вспомогательного массива С, C[j] = 0; // использующегося в качестве счетчика

for j = n - 1 to 0 // заполняем вспомогательный массив B, в котором после каждой итерации B[C[digit(A[j], i)]] = A[j]; // внешнего цикла числа отсортированы по младшим i битам