Motivation

Сортировка подсчетом (Counting Sort) никогда не сравнивает два элемента. Она использует их значения напрямую в качестве индексов в массиве count, что позволяет ей работать за линейное время.

Зачем изучать сортировку подсчетом?

• Линейное время: она работает за O(n + k), где n — количество элементов, а k — диапазон значений. Когда k мало, это быстрее, чем O(n log n).
• Устойчивость (при правильной реализации): основа для поразрядной сортировки (Radix Sort), которая последовательно применяет несколько проходов сортировки подсчетом.
• Другой подход: сортировка путем подсчета количества вхождений значений, а не их сравнения.

Компромисс: ей требуется O(k) памяти для массива count, поэтому она плохо подходит, когда диапазон значений огромен (например, при сортировке нескольких чисел в диапазоне до миллиарда).