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

     Идея алгоритма заключается в простом подсчете количества вхождений каждого числа в массив. Это делается так: выполним один проход массива и для каждого числа из отрезка [0, max] подсчитаем сколько раз оно встретится. Вычисленные количества сохраним в специальном массиве счетчиков. Затем запишем в массив - результат (а это может быть и исходный массив) каждое число столько раз, чему равно значение соответствующего ему счетчика, то есть, сколько раз оно встретилось.

Назовем Исходный массив - Массивом. Пусть в Массиве N - элементов лежащих в отрезке [0, max]

Алгоритм

Для всех элементов Массива делать

    Счетчик с номером равным текущему элементу увеличить на 1

Индекс =0

Для всех Чисел от 0 до max делать

    Номер = 0

    Пока Номер < Очередного счетчика делать

        Элемент Массива с Индексом = Числу

        Номер увеличить на 1

        Индекс увеличить на 1

    Заметим, что для этого алгоритма необходим вспомогательный массив, размер которого зависит не от количества элементов в массиве, а от значения максимального элемента. Поэтому данный алгоритм можно использовать только при относительно небольших значениях max.

 Текст программы