Spreadsort

Проблема

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

Решение

Для текущего диапазона элементов вычисляется его размер. Если размер мал (например, не больше некоторого порога вроде 16), диапазон сортируется напрямую сортировкой вставками - для маленьких групп накладные расходы на организацию корзин того не стоят. Иначе элементы распределяются по корзинам по значению (как в корзинной сортировке), число корзин выбирается адаптивно (например, порядка квадратного корня от размера диапазона), а затем каждая заполненная корзина рекурсивно обрабатывается тем же способом - снова либо распределением, либо прямой сортировкой, в зависимости от её итогового размера.

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

Ключевая константа реализации - THRESHOLD = 16 (строка 4): порог, ниже которого диапазон сортируется вставками, а не распределяется по корзинам. Число выбрано не произвольно - на группах примерно такого размера накладные расходы на создание массива корзин (Array.from, строка 34) и заполнение их элементами обычно перевешивают выигрыш от распределения, а сортировка вставками на 16 элементах выполняется практически мгновенно.

Индекс корзины для элемента вычисляется как Math.floor((a[i] - min) / span) (строка 36), где span = (max - min + 1) / bucketCount (строка 33) - это линейная интерполяция значения в диапазон корзин, тот же принцип, что и в обычной корзинной сортировке, но границы min/max пересчитываются заново на каждом уровне рекурсии (строки 25-29) для текущего поддиапазона, а не берутся из исходного массива целиком.

Число корзин bucketCount = Math.max(2, Math.floor(Math.sqrt(size))) (строка 32) растёт как квадратный корень от размера диапазона - компромисс между слишком малым числом корзин (тогда в каждой окажется много элементов, и рекурсия почти не помогает) и слишком большим (тогда много корзин будут почти пустыми, а накладные расходы на их создание не окупятся). Оригинальный алгоритм Спредсорт Стивена Росса использует более точную формулу на основе логарифма разброса битового представления ключей, а не просто квадратный корень от размера - упрощение сделано ради учебной ясности.

После распределения по корзинам их содержимое записывается обратно в массив по порядку (строки 41-46), а затем каждый записанный сегмент рекурсивно передаётся в `sortRange` (строка 45) - именно эта повторная проверка размера и решения «распределять или сортировать вставками» защищает от вырождения на сильно неравномерных данных: перегруженная корзина не остаётся неотсортированной, а обрабатывается заново тем же способом, пока не станет достаточно маленькой.

Пример на диапазоне из 25 элементов со значениями от 0 до 99: bucketCount = max(2, floor(sqrt(25))) = 5, span = (99 - 0 + 1) / 5 = 20. Корзина 0 получает значения [0, 20), корзина 1 - [20, 40) и так далее. Если все 25 значений равномерно распределены, в каждой корзине окажется примерно по 5 элементов - меньше порога 16, и они сразу сортируются вставками без дальнейшей рекурсии.

Проверка if (min === max) return (строка 30) не просто оптимизация - она обязательна для корректности: без неё диапазон из одинаковых значений дал бы span = 0, деление на ноль в вычислении индекса корзины и, как следствие, некорректное поведение или бесконечную рекурсию (все элементы снова и снова попадали бы в диапазон без прогресса).

Средняя сложность O(n log(k/s)) отражает именно этот процесс: k - примерная битовая ширина диапазона значений ключа, s - порог перехода на сортировку вставками (аналог THRESHOLD). Чем больше исходный разброс значений (больше k) и чем меньше порог (меньше s), тем глубже рекурсия распределения - но каждый уровень стоит O(n) на распределение и запись назад, а глубина ограничена логарифмом отношения k/s, а не n, что и даёт выигрыш перед O(n log n) при достаточно равномерных данных.

Алгоритм разработан Стивеном Дж. Россом в 2002 году (диссертация и статья "Adaptive Distribution-Based Sorting") как попытка получить производительность корзинной сортировки без риска её худшего случая - той же цели, что и у смузсорта относительно heap sort, но решённой через комбинацию распределения и сравнений, а не через структуру кучи.

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

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

Предпочесть Спредсорт корзинной сортировке, когда распределение данных заранее неизвестно или может быть враждебным (специально подобранным) - обычная корзинная сортировка деградирует до O(n²) там, где Спредсорт остаётся на уровне O(n log n).

Предпочесть поразрядную сортировку Спредсорту, если ключи - целые числа фиксированной битовой ширины с известной структурой: radix sort проще, не требует деления и не пересчитывает min/max на каждом уровне.

Не стоит применять на маленьких массивах (n не больше пары сотен элементов) - расходы на вычисление min/max и распределение по корзинам не окупаются; проще сразу использовать insertion sort или встроенную сортировку языка.

Хороший выбор в высокопроизводительных C++/системных библиотеках, сортирующих числа с плавающей точкой или целые числа большими партиями, где даже небольшой выигрыш над O(n log n) заметен на масштабе.

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

Стивен Дж. Росс, 2002 - диссертация и статья "Adaptive Distribution-Based Sorting", описывающая Спредсорт как обобщение корзинной и поразрядной сортировок с адаптивным выбором стратегии.

Документация Boost.Sort приводит собственные бенчмарки, сравнивающие Спредсорт с std::sort (introsort) на разных типах числовых данных, показывая выигрыш именно на больших объёмах данных с широким диапазоном значений.

Алгоритм часто фигурирует в статьях о семействе гибридных распределяющих сортировок (наряду с American flag sort и bucket sort) как пример адаптивного выбора между распределением и сравнением без ручной настройки под конкретный набор данных.

Обсуждается в материалах о сортировке чисел с плавающей точкой как пример алгоритма, который работает с IEEE 754 значениями напрямую (после соответствующего преобразования порядка битов), не сводя задачу к целочисленной поразрядной сортировке.

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

• При сортировке больших объёмов числовых данных, распределение которых заранее неизвестно и может быть как равномерным, так и сильно скошенным - там, где чистая корзинная сортировка рискованна, а сортировка сравнениями заведомо не использует структуру данных.
• В высокопроизводительных библиотеках общего назначения (сортировка чисел с плавающей точкой, целых чисел), где нужна одна реализация, устойчиво работающая быстрее O(n log n) в среднем случае без ручной настройки под конкретные данные.

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

• Библиотека Boost.Sort (C++) включает промышленную реализацию Спредсорт как одну из доступных стратегий сортировки, применяемую как более быстрая альтернатива std::sort на подходящих числовых данных.
• Обработка больших массивов геопространственных или сенсорных данных нередко использует гибридные распределяющие сортировки вроде Спредсорт, поскольку значения там часто числовые и допускают адаптивное разбиение на корзины.