How it works?

Сортировка подсчетом (Counting Sort) работает в две фазы: подсчет, затем пересборка.

Пошаговый процесс:

1. Подсчет: создайте массив count, где count[v] — это количество вхождений значения v.
2. Пересборка: пройдите по значениям от наименьшего к наибольшему и запишите каждое значение v в выходной массив count[v] раз.

Пример для [4, 2, 2, 8, 3, 3, 1]:

• Подсчитайте каждое значение: 1 встречается один раз, 2 дважды, 3 дважды, 4 один раз, 8 один раз.
• Пересборка по порядку: [1, 2, 2, 3, 3, 4, 8].

Сравнения не производились: само значение определяло, куда попадает каждый элемент.