Time and Space Complexity

Временная сложность:

• O(n + k)
  • где n — количество элементов, а k — диапазон значений (max + 1). Один проход для подсчета, один проход по счетчикам для пересборки.
• Когда k мало и фиксировано, это фактически O(n), что быстрее, чем O(n log n) сортировок сравнением.

Пространственная сложность:

• O(n + k)
  • Массив счетчиков использует O(k), а выходной массив — O(n).

Резюме:

• Сортировка подсчетом (Counting Sort) — это стабильная сортировка без сравнения, которая работает за линейное время для небольших диапазонов целых чисел.
• Она плохо подходит, когда диапазон значений k очень велик, так как массив счетчиков будет огромным. Эта версия предполагает использование неотрицательных целых чисел.