Сортировка подсчётом и поразрядная

В каталоге USGS 19 073 землетрясения силой от 5 за 2015–2025 годы. Сортировка слиянием упорядочит их по магнитуде за 255 585 сравнений. Но магнитуда записана с точностью до сотых и лежит между 5,00 и 8,80 — у неё всего 381 возможное значение. Заведём по счётчику на каждое и посчитаем, сколько землетрясений какой силы. Тогда ответ можно выписать сразу: сначала все 5,00, потом все 5,01, и так до 8,80. Ни одного сравнения.

Весь подсчёт — 38 527 шагов: проход по каталогу, 381 сложение и ещё один проход. Обратите внимание на счётчики магнитуд. На логарифмической шкале они выстраиваются почти по прямой: землетрясений силой от 5,0 до 5,9 — 17 595, от 6,0 до 6,9 — 1325, от 7,0 до 7,9 — 145, от 8,0 и выше — 8. С каждой единицей магнитуды примерно вдесятеро меньше — это закон Гутенберга — Рихтера, и сортировка строит его гистограмму по дороге. Переключите ключ на глубину: высокий пик на 10 км — не геология, а соглашение каталога. Если глубину не удаётся определить по записям станций, USGS ставит условные 10 км.

Идея

Если ключи — целые числа из небольшого диапазона, сравнивать их незачем. Посчитаем, сколько элементов с каждым ключом; префиксные суммы этих счётчиков скажут, с какого места в ответе начинается блок каждого ключа; вторым проходом положим каждый элемент на первое свободное место своего блока. Если ключи длинные, разобьём их на цифры и отсортируем подсчётом по каждой цифре — по одной за проход.

У сортировки подсчётом три шага, и каждый простой.

1. Счёт. Массив count из k нулей; для каждого элемента — count[key] += 1.
2. Адреса. Префиксные суммы: start[v] = сколько элементов с ключом меньше v. Это номер ячейки, с которой в ответе начнётся блок ключа v.
3. Раскладка. Идём по входу слева направо; элемент с ключом v кладём в out[start[v]] и увеличиваем start[v].

В третьем шаге и прячется главное свойство. Элементы с равными ключами встают в свой блок в том же порядке, в каком шли во входе, — сортировка устойчива. В первой сцене это видно по цвету: каталог идёт по времени, и внутри каждого блока цвета переходят от тёмного к светлому. Переключите раскладку на «с конца блока»: ответ по-прежнему отсортирован по магнитуде, но внутри блоков время пошло вспять. Для одной сортировки разница может быть и неважна. Для поразрядной она решает всё.

А как же n log n

Любая сортировка, которая узнаёт о данных только из сравнений «меньше или нет», в худшем случае делает не меньше log₂ n! ≈ n log₂ n − 1,44n сравнений: каждое сравнение — ответ «да» или «нет», а перестановок n!. Доказательство — в статье о нижней границе. Сортировка подсчётом этой границе не противоречит, потому что играет в другую игру. Строка count[key] += 1 — это вопрос с 381 вариантом ответа, на который машина отвечает за одно обращение к памяти: адрес ячейки и есть ответ.

Платить приходится диапазоном ключей. Время и память — O(n + k), и при k намного больше n работа уходит на пустые счётчики. Выберите в первой сцене ключ «время»: секунд с начала 2015 года до последнего события каталога — 347 120 818, по счётчику на каждую — это в 18 тысяч раз больше, чем землетрясений. Такой ключ подсчётом не отсортировать. Но его можно разложить на части.

По цифре за проход

Задолго до компьютеров перфокарты сортировали машиной, которая за один проход читала одну колонку и раскладывала карты по карманам с цифрами от 0 до 9. Чтобы упорядочить карты по многозначному полю, оператор пропускал колоду через машину несколько раз, начиная с правой, младшей колонки поля, и после каждого прохода собирал карманы по порядку. Ниже — шестнадцать землетрясений 2025 года силой от 7, по времени суток: четыре цифры, четыре прохода.

Почему начинать с младшей цифры, а не со старшей, как сравнивают числа люди? Переключите порядок проходов и посмотрите на результат: колода упорядочена только по последней прочитанной цифре. Каждый проход заново раскладывает колоду, и от прошлых проходов остаётся лишь порядок внутри кармана. Значит, последний проход должен быть главным — по старшей цифре.

Без устойчивости доказательство рассыпается на втором случае, и сама сортировка тоже. Отсюда и выбор сортировки для прохода: подсчётом — устойчивая, линейная и как раз для цифр, у которых мало значений.

Так получается поразрядная сортировка от младшей цифры, LSD (least significant digit). Цифры в компьютере удобно брать двоичные: 32-битное число — это четыре байта, четыре прохода по 256 счётчиков. Листинг radix ниже возвращает каталог, отсортированный по силе, обратно в порядок времени: ключ — секунды с 2015 года, четыре прохода по байту. Вход почти упорядочен — магнитуд всего 83, внутри каждой события и так идут по времени, — и соседей не по порядку в нём всего 69. А после первого прохода их 3089, после второго 9413, после третьего 8340 и только после четвёртого — ноль. Поразрядной сортировке безразлично, насколько упорядочен вход: порядок проступает только на последнем проходе.

Ширину цифры выбирают сами. Цифра из b бит даёт ⌈32/b⌉ проходов по 2^b счётчиков: при b = 8 — четыре прохода по 256, при b = 16 — два по 65 536. Меньше проходов — меньше чтений массива, но больше счётчиков, и когда массив счётчиков перестаёт помещаться в кэш первого уровня, раскладка начинает промахиваться мимо кэша. Байт — частый выбор: 256 счётчиков занимают пару килобайт и не покидают кэш.

Строки: со старшего символа

У строк разная длина, и младшего разряда у них нет. Зато есть старший — первый символ. Разложим строки по первому символу в корзины; внутри каждой корзины у всех строк одинаковое начало, и порядок между корзинами уже верный. Каждую корзину раскладываем по второму символу, и так далее, пока в корзине не останется одна строка. Это сортировка от старшего разряда, MSD (most significant digit), и по сути она на ходу строит бор: корзины — его узлы.

Ниже — адреса всех 8966 страниц этого сайта из его карты. Нажимайте на корзины и спускайтесь: разделы сайта, потом английские версии страниц, учебники, конвертер единиц.

Сортировке со старшего символа понадобилось 252 849 взглядов на символ. Сортировка слиянием сделала 99 160 сравнений и прочитала в них 1 824 994 символа — в 7,2 раза больше. Дело в общих началах. Чтобы сравнить /en/utilities/unit-converter/square-centimeter-to-square-mile и …-to-square-millimeter, сравнение читает 60 одинаковых символов, и в следующем сравнении с соседним адресом — снова те же 60. Поразрядная сортировка читает каждый символ каждой строки не больше одного раза и останавливается, как только строка оказалась в корзине одна. Меньше прочитать нельзя: любая сортировка должна дочитать каждую строку до места, где она отличается от соседей.

У MSD есть и слабость: на каждом уровне она заводит 128 или 256 корзин, даже если в корзине три строки. Поэтому в настоящих реализациях маленькие корзины досортировывают вставками. Известный вариант без второго массива — American flag sort из статьи «Engineering Radix Sort» Питера Макилроя, Кита Бостика и Дугласа Макилроя (1993): там подсчёт определяет границы корзин, а элементы переставляются по своим корзинам циклами прямо на месте. Авторы писали, что их сортировки строк обычно хотя бы вдвое быстрее хорошей быстрой сортировки.

Код

Сортировка подсчётом на всём каталоге. Чтобы не связываться с дробями, магнитуда читается из текста сразу в сотых: «5.36» → 536. Проверка в конце — что ответ совпал с ответом устойчивого слияния до элемента.

Поразрядная сортировка — это сортировка подсчётом в цикле по цифрам. Сначала сортировщик перфокарт из второй сцены, потом весь каталог по секундам, по байту за проход:

И строки со старшего символа: карта сайта, счётчики прочитанных символов у обеих сортировок и самые похожие соседи в ответе.

Сколько это стоит

Для 32-битных чисел d = 4 при байтовых цифрах, и поразрядная сортировка линейна: четыре прохода подсчёта и четыре раскладки, какое бы n ни было. Сортировке сравнениями на миллионе чисел нужно около 20 сравнений на элемент, поразрядной — восемь проходов по массиву, четыре подсчёта и четыре раскладки, без единого сравнения. Замер на случайных 32-битных числах:

На Go поразрядная сортировка в двадцать строк обгоняет slices.Sort в два — два с половиной раза: на миллионе чисел 51 мс против 127, на десяти миллионах — 474 мс против 1150. На Python всё наоборот: наша поразрядная в 3–4,5 раза медленнее sorted. Каждый её шаг — строка интерпретатора, а sorted написана на C, и интерпретатор съедает весь выигрыш в числе операций. Поэтому библиотеки, которым скорость важна, пишут поразрядную сортировку на C. В numpy устойчивая сортировка массива целых чисел до 16 бит — np.sort(a, kind="stable") для int8, int16 и их беззнаковых родственников — это поразрядная сортировка, а для остальных типов — Timsort.

Где она не годится

• Ключ должен быть числом или строкой цифр. Сортировать подсчётом можно то, что превращается в номер ячейки. Отрицательные целые сдвигают: у 32-битного числа достаточно инвертировать знаковый бит, и порядок беззнаковых чисел совпадёт с порядком знаковых. Числа с плавающей точкой тоже сводятся к целым битовым приёмом — у положительных инвертируют знаковый бит, у отрицательных все биты, — так их сортирует, например, DeviceRadixSort в библиотеке CUB для видеокарт.
• Сравнение произвольной функцией недоступно. Сортировать записи по составному правилу «по городу, а при равенстве по убыванию даты» поразрядной можно, только если сначала закодировать правило в ключ.
• Нужна вторая память. LSD раскладывает во второй массив той же длины. Варианты на месте есть — тот же American flag sort, — но они неустойчивы и потому годятся для MSD, а не для LSD.
• Маленькие массивы и длинные ключи. Четыре прохода по 256 счётчиков на массив из 50 чисел — это 1024 сложения префиксных сумм ради 50 элементов. Для 64-битных ключей проходов уже восемь — вдвое больше работы, — а сортировке сравнениями длина ключа почти безразлична.

Где она работает

Git. Каждый пакет объектов git сопровождает индекс, и он начинается с таблицы fan-out из 256 чисел: N-е число — сколько объектов в пакете имеют первый байт имени не больше N. Это в точности префиксные суммы сортировки подсчётом по первому байту. Дальше в индексе лежат отсортированные имена объектов, и чтобы найти объект, git берёт его первый байт, по двум соседним числам таблицы находит отрезок, где лежат все имена с этим байтом, и ищет двоичным поиском уже внутри него.

Видеокарты. Поразрядная сортировка разбивается на независимые куски: каждый поток считает свою часть гистограммы, префиксные суммы считаются параллельно. Поэтому поразрядная сортировка хорошо ложится на видеокарты: в библиотеке CUB от NVIDIA для этого есть DeviceRadixSort.

Суффиксные массивы. Чтобы искать подстроки в длинном тексте или геноме, суффиксы текста сортируют. Классический способ — удвоение: отсортировать суффиксы по первым 1, 2, 4, 8, … символам, где каждый шаг — сортировка пар уже известных рангов. Пары — это двузначные числа, и их удобно сортировать поразрядно, двумя проходами подсчётом. Так и устроена вторая задача этой статьи.

Данные с маленьким диапазоном. Баллы экзамена, возраст, коды символов, оценки от 1 до 5, гистограммы яркости изображения — везде, где значений мало, а элементов много, подсчёт — самый быстрый и самый простой способ. Пример с баллами выпускников разобран в главе курса «Турнир сортировок».

История

Поразрядная сортировка старше компьютеров. Герман Холлерит строил табуляторы для переписи населения 1890 года, а к следующей переписи понадобилось сортировать карты, и в 1901 году его фирма выпустила сортировальную машину. Сортировщики перфокарт IBM потом десятилетиями делали ровно одно: читали одну колонку и раскладывали карты по карманам; модель 82 1949 года пропускала 650 карт в минуту. Многоколоночные поля операторы сортировали от младшей колонки к старшей — LSD в чистом виде, с устойчивостью, которую обеспечивала сама механика: карты в кармане ложатся в том порядке, в каком пришли.

На ЭВМ поразрядная сортировка поначалу казалась неудобной: сколько места отводить под каждую корзину, если заранее неизвестно, сколько в неё попадёт? В 1954 году Гарольд Сьюард в магистерской диссертации предложил сначала пройти по данным и посчитать размеры корзин, а потом раскладывать элементы прямо на их окончательные места в одном массиве. Это и есть сортировка подсчётом — и её устойчивость сделала поразрядную сортировку на компьютере такой же простой, как на сортировщике карт.

Задачи

Первая — разминка с подвохом: IP-адреса выглядят как строки, а сортировать их надо как числа. Вторая — суффиксный массив генома удвоением, где каждый шаг — поразрядная сортировка пар.