Postman Sort

Проблема

Классическая поразрядная сортировка (LSD radix sort) обрабатывает цифры от младшей к старшей - это просто и корректно, но требует пройтись по всем разрядам числа даже тогда, когда после первых нескольких проходов данные уже почти разложены по группам. Хочется способа сортировки по цифрам, начиная с самой значимой - так, как естественно раскладывают почту: сначала грубая раскладка по первому разряду индекса, а внутри каждой такой группы отдельно и независимо уточняется порядок по следующим разрядам.

Решение

Массив делится на 10 корзин по значению самой значимой (старшей) незадействованной цифры каждого числа. Затем для каждой заполненной корзины рекурсивно применяется тот же приём - деление на 10 корзин, но уже по следующей, менее значимой цифре - до тех пор, пока не будут исчерпаны все разряды или в корзине не останется не более одного элемента. Такая раскладка «от старшего разряда к младшему» (most-significant-digit-first) точно соответствует тому, как почтовая машина раскладывает письма: грубая сортировка по первой цифре индекса, а затем всё более точная - по следующим.

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

Проследим раскладку на массиве трёхзначных чисел [329, 457, 65, 839, 436, 720, 355] (n = 7, maxDigits = 3). Первый проход идёт по сотням (exp = 100): 329→3, 457→4, 65→0, 839→8, 436→4, 720→7, 355→3. Корзины: 0:[65], 3:[329,355], 4:[457,436], 7:[720], 8:[839]. После сборки массив становится [65, 329, 355, 457, 436, 720, 839].

Из семи чисел три - 65, 720, 839 - попали в корзины размером ровно 1, поэтому рекурсивный вызов для них немедленно завершается на строке 9 (hi - lo <= 1), даже несмотря на то что впереди ещё два неиспользованных разряда. Продолжают раскладку только две группы: [329, 355] и [457, 436] - по два элемента каждая.

Второй проход (десятки, exp = 10) обрабатывает только эти 4 оставшихся элемента: 329→2, 355→5 в одной группе и 457→5, 436→3 в другой. После раскладки обе группы уже полностью упорядочены - [329, 355] и [436, 457] - и рекурсия для единиц (digitIndex = 0) не нужна вообще: каждая корзина второго прохода тоже получилась размером 1.

Итого на весь пример потребовалось всего 11 вычислений цифры (7 на первом проходе + 4 на втором), хотя LSD radix sort того же массива сделал бы честные 3 прохода по всем 7 элементам - 21 вычисление цифры, то есть почти вдвое больше. Разница растёт с ростом доли «уникальных с первого взгляда» чисел во входе - каждое такое число экономит все оставшиеся разряды.

Асимптотика в худшем случае, однако, не выигрывает у LSD: если все n чисел совпадают вплоть до последнего разряда (например, 100, 101, ..., 100 + n - 1), каждый из k уровней рекурсии проходит по всем n элементам, и суммарная работа - O(n · k), совпадая с LSD. Выигрыш MSD - это выигрыш по константе на «удачных» данных, а не по асимптотическому классу.

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

Раскладка MSD-first неявно строит структуру, эквивалентную дереву trie глубиной k: каждый уровень рекурсии - это один уровень дерева, а узлы на этом уровне - это 10 возможных значений очередной цифры. Числа, разошедшиеся по разным поддеревьям на раннем уровне, никогда больше не сравниваются друг с другом - ровно так же, как строки с разными префиксами не встречаются в одной ветке символьного trie.

Итог: почтовая сортировка не меняет асимптотику LSD-варианта, но меняет то, *когда* выполняется работа - грубая раскладка сначала, уточнение только там, где оно ещё нужно. Это делает её удачной моделью того, как реальные системы (почтовая логистика, префиксные индексы) устроены на практике: сначала используется самая информативная часть ключа, а точная доработка откладывается до тех пор, пока она действительно требуется.

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

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

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

Как основа для сортировки строк по префиксу - тот же MSD-принцип с побуквенной раскладкой вместо поразрядной лежит в основе быстрой лексикографической сортировки словарей и списков URL, где важен именно префикс.

Не стоит использовать, если глубина рекурсии (число разрядов k) непредсказуема или очень велика относительно n - накладные расходы на создание 10 корзин на каждом уровне рекурсии для малых групп могут перевесить выигрыш от ранней остановки.

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

Автоматизированные системы сортировки почты (например, оборудование USPS и Deutsche Post) физически организованы как многоуровневая MSD-раскладка: письма сначала грубо распределяются по региону (первые цифры индекса), затем внутри каждого региона - по более мелким зонам, и лишь на последнем уровне - по конкретному отделению.

Файловые системы и базы данных с префиксным индексированием (B-деревья и trie-структуры, например в LevelDB/RocksDB) применяют тот же принцип «сначала самая значимая часть ключа», распределяя записи по диапазонам префиксов прежде, чем уточнять порядок внутри диапазона.

Маршрутизация телефонных звонков по коду страны и коду города использует ту же логику MSD: коммутатор сначала грубо направляет звонок по первым цифрам номера, а точная маршрутизация к абоненту происходит на более позднем, локальном этапе.

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

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

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

• Почтовые сортировочные машины (mail sorting machines), используемые почтовыми службами по всему миру, физически раскладывают письма по лоткам сначала по первым цифрам индекса, а затем уточняют раскладку по следующим цифрам - именно этот процесс и дал алгоритму название.
• MSD radix sort в базах данных и системах с префиксными индексами (например, сортировка строк по префиксу) применяет тот же принцип «сначала самая значимая часть ключа», что удобно сочетается со структурами данных вроде trie.