Time and Space Complexity

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

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

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

• O(n + k)
  • На каждом проходе создается выходной массив размера n и массив счетчиков размера k.

Итог:

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