Сортирвка подсчетом:
Эта сортировка применяется, если диапазон сортируемых значений невелик(где-то до 16-bit INT). Идея алгоритма - за один проход по массиву подсчитать, сколько раз встретилось каждое значение и затем вывести значения в соответствующем порядке столько раз, сколько оно встретилось. Сложность алгоритма - O(N)