Radix Sort

Проблема

Сортировка подсчётом быстра, но требует O(k) памяти, где k - диапазон значений; для чисел вроде номеров телефонов или паспортов (миллиарды возможных значений) это неприменимо, даже если элементов всего несколько тысяч. Нужен способ получить линейное время без создания счётчика на весь диапазон значений.

Решение

Вместо того чтобы считать по всему значению целиком, алгоритм сортирует числа по одному разряду за раз, начиная с младшего (единицы, затем десятки, затем сотни и т.д.). Каждый проход - это устойчивая сортировка подсчётом с диапазоном ключей всего 0-9 (или 0 - (основание системы счисления − 1)), поэтому счётчик всегда маленький и фиксированного размера. Устойчивость критична: она гарантирует, что порядок, установленный на предыдущих (менее значимых) разрядах, не разрушается при сортировке по следующему, более значимому разряду. После обработки всех разрядов самого длинного числа массив полностью отсортирован.

Как это работает

Проследим все три прохода на массиве [170, 45, 75, 90, 802, 24, 2, 66] (n = 8, max = 802, значит 3 разряда). Проход по единицам (exp = 1) даёт [170, 90, 802, 2, 24, 45, 75, 66] - обратите внимание, что 170 и 90 (оба с цифрой единиц 0) сохранили свой исходный взаимный порядок, как и 45 и 75 (оба с цифрой 5).

Проход по десяткам (exp = 10) берёт результат первого прохода как есть и даёт [802, 2, 24, 45, 66, 170, 75, 90]. Здесь видна цена неустойчивости: 802 и 2 оба имеют цифру десятков 0, и их порядок (802 перед 2) - это в точности порядок, унаследованный от конца первого прохода, а не случайность. Если бы распределение по корзинам не было устойчивым, это наследование сломалось бы, и результат перестал бы быть корректным после третьего прохода.

Финальный проход по сотням (exp = 100) даёт [2, 24, 45, 66, 75, 90, 170, 802] - массив полностью отсортирован. Цикл останавливается на следующей проверке: Math.floor(802 / 1000) === 0, значит exp = 1000 уже превышает max, и четвёртый проход не нужен.

Каждый проход стоит O(n + 10): O(n) на раскладку по корзинам плюс O(10) на сборку 10 корзин обратно (в общем случае - O(n + k), где k - основание системы счисления). При d = 3 прохода общая стоимость - O(3 · (n + 10)) = O(d · (n + k)), в точности заявленная асимптотика.

В отличие от MSD-варианта (postman-sort в этом курсе), здесь число проходов d не зависит от того, насколько быстро числа расходятся по значению - все n элементов проходят через все d раундов раскладки безусловно. Это делает LSD проще (без рекурсии, без явного отслеживания диапазонов), но лишает его возможности завершить обработку части данных раньше срока.

Выбор основания k = 10 удобен для примеров, но не оптимален: для 32-битных целых чисел основание k = 256 (один байт) требует всего d = 4 прохода вместо d = 10 при основании 10 (для чисел до ~4 миллиардов). Компромисс - больше памяти на корзины за проход (256 вместо 10), но меньше самих проходов, и битовые операции для извлечения байта ((value >> (8 * i)) & 0xFF) быстрее деления по основанию 10.

Формальный анализ LSD- и MSD-поразрядной сортировки, включая терминологию «radix sort» и доказательство корректности через устойчивость промежуточных проходов, приведён в Дональде Кнуте (Donald Knuth), «The Art of Computer Programming, Volume 3: Sorting and Searching» (1973, раздел 5.2.5) - это же издание формализовало и нижнюю границу Ω(n log n) для сортировок сравнением, от которой поразрядная сортировка как раз свободна.

Итог: поразрядная сортировка обходит нижнюю границу Ω(n log n), потому что вообще не сравнивает элементы друг с другом - она читает цифры и раскладывает по корзинам, и цена этого - линейная зависимость от d, числа разрядов, а не от log n. Пока d ограничено (32-битные числа, почтовые индексы, IP-адреса), это выгодный обмен; для ключей с непредсказуемо большим или переменным числом разрядов выигрыш исчезает.

Нюансы выбора

Фиксированное, небольшое основание k - например, байтовое основание 256 для 32/64-битных целых чисел даёт предсказуемое малое d (4 или 8 проходов) и хорошо ложится на битовые операции вместо деления.

Против MSD-варианта (`postman-sort`) - если ключи в основном одинаковой длины и не расходятся рано по значению, простота LSD (без рекурсии) перевешивает потенциальную экономию MSD на ранней остановке; для сильно неравномерных данных выигрывает MSD.

Многоключевая сортировка (сначала по фамилии, затем по имени) - устойчивость каждого прохода позволяет буквально прогнать сортировку по каждому ключу от наименее значимого к наиболее значимому, получив корректный составной порядок без единой явной функции сравнения.

Избегать при переменной длине ключей - строки или числа сильно разной длины требуют выравнивания (дополнения нулями/пробелами до общей длины) перед LSD-проходами; для таких данных MSD-подход без выравнивания обычно естественнее.

Примеры в коде

Donald Knuth, «The Art of Computer Programming, Volume 3: Sorting and Searching» (1973, раздел 5.2.5) - формальный источник термина «radix sort» и анализа LSD/MSD-вариантов.

Jon Bentley, Robert Sedgewick, «Fast Algorithms for Sorting and Searching Strings» (1997) - строит на поразрядном подходе алгоритмы сортировки строк (three-way radix quicksort, MSD string sort), обобщая «разряд» на символ строки.

GPU-библиotеки сортировки (например, NVIDIA Thrust) используют поразрядную сортировку как реализацию по умолчанию для примитивных числовых ключей - у неё нет зависящих от данных ветвлений, что делает её удобной для параллельного исполнения на тысячах ядер.

Алгоритм построения суффиксного массива DC3/skew (Kärkkäinen, Sanders, 2003) использует поразрядную сортировку как линейную по времени подпрограмму для сортировки троек символов - без неё заявленная линейная сложность DC3 была бы недостижима.

Когда применять

• Для сортировки больших массивов целых чисел ограниченной разрядности - идентификаторов, телефонных номеров, почтовых индексов.
• Как основа для LSD-сортировки строк одинаковой длины, где «разряд» - это символ в определённой позиции.

Примеры из практики

• Сортировка карточек в механических табуляторах (США, перепись населения 1890 года) - исторически первое массовое применение идеи поразрядной сортировки, ещё до появления компьютеров.
• Сортировка IP-адресов и MAC-адресов в сетевом оборудовании часто использует поразрядный подход из-за фиксированной битовой длины ключей.