Motivation

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

Зачем изучать Radix Sort?

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

Компромисс: ей требуются ключи, которые можно разбить на разряды (в данном случае — неотрицательные целые числа), и дополнительная память для корзин (buckets).