Bucket Sort

Проблема

Сортировка подсчётом и поразрядная сортировка отлично работают с целыми числами, но что делать с равномерно распределёнными вещественными числами, скажем, в диапазоне [0, 1)? Считать по каждому значению бессмысленно - значений бесконечно много. Нужен способ использовать знание о распределении данных, не требуя дискретных ключей.

Решение

Диапазон возможных значений делится на k равных интервалов - «корзин». Каждый элемент попадает в корзину, соответствующую его значению (например, floor(value * k) для чисел из [0, 1)). Если исходные данные распределены равномерно, в каждой корзине окажется примерно n/k элементов - небольшое количество, которое можно быстро отсортировать простым алгоритмом (обычно insertion sort, эффективным на маленьких массивах). После сортировки всех корзин их содержимое просто соединяется по порядку от первой к последней - результат уже отсортирован.

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

Заявленная средняя сложность O(n + k) верна только при скрытом допущении: число корзин k должно быть примерно пропорционально n, чтобы на каждую корзину в среднем приходился O(1) элемент. Реализация на этой странице задаёт bucketCount по умолчанию как ⌈√n⌉, а не как n - разберём, что это меняет в реальной асимптотике.

Модель «шаров по урнам» даёт точную формулу: если n элементов случайно и равномерно раскиданы по k корзинам, ожидаемое значение суммы квадратов размеров всех корзин равно примерно n + n²/k (дисперсия биномиального распределения плюс квадрат среднего, просуммированные по k корзинам). Сумма квадратов важна именно потому, что insertion sort на корзине из m элементов в среднем делает порядка m² сравнений - значит, суммарная работа всех корзин пропорциональна этой же n + n²/k.

Подставим числа. При k = n сумма даёт n + n²/n = 2n - линейная работа, ради которой блочная сортировка и задумывалась. При выборе из этой реализации, k = √n, та же формула даёт n + n²/√n = n + n^1.5. Для n = 1 000 000 это n^1.5 = 10⁹ - примерно в 500 раз больше, чем 2n = 2 000 000 операций при k = n.

Это не ошибка, а осознанный компромисс. При k = n пришлось бы выделить n почти пустых массивов - большинство содержало бы 0 или 1 элемент, и накладные расходы на создание и обход стольких мелких объектов на практике часто перевешивают выигрыш от более быстрой внутренней сортировки. `√n` корзин - популярный практический баланс между размером корзины и их количеством, применяемый во многих реализациях, даже ценой худшей асимптотики на бумаге.

Индекс корзины вычисляется как floor((value - min) / range). Добавка + 1 к (max - min) в формуле range нужна, чтобы для максимального элемента idx получался строго меньше bucketCount - без неё value === max дал бы idx === bucketCount, что вышло бы за границы массива корзин. Из-за неточности чисел с плавающей точкой даже с этой поправкой округление на пограничных значениях иногда может дать idx === bucketCount, поэтому строка if (idx >= bucketCount) idx = bucketCount - 1 - не избыточная подстраховка, а необходимая защита от выхода за границу.

Поскольку индекс всегда считается через (value - min), алгоритм одинаково работает для отрицательных чисел, дробей и любых сдвинутых диапазонов - в отличие от counting sort, которому нужны неотрицательные целые ключи в разумных пределах. Единственное жёсткое требование - значения должны поддерживать вычитание и сравнение, то есть быть числами.

Худший случай виден на конкретном примере: массив из 1000 чисел, где 990 значений лежат в диапазоне [0, 0.01), а оставшиеся 10 - равномерно раскиданы по [0.01, 1). При 32 корзинах диапазон первой корзины - [0, 1/32) ⊃ [0, 0.01) - поглотит почти все 990 «тесных» значений, и insertion sort на корзине из ~990 элементов сделает порядка 990² ≈ 980 000 сравнений, против нескольких десятков во всех остальных корзинах вместе взятых. Равномерность распределения - не формальность в описании алгоритма, а условие, без которого блочная сортировка вырождается в insertion sort с лишним шагом группировки.

Название «bucket sort» (иногда «bin sort») закрепилось в литературе к 1970-м годам; Дональд Кнут описывает эту семью распределяющих сортировок в третьем томе The Art of Computer Programming (1973) как естественное развитие сортировки подсчётом на непрерывные значения. Более поздний родственник - flashsort Карла-Дитриха Нойберта (1998, статья в Dr. Dobb's Journal) - идёт дальше: вычисляет индекс корзины по единственной формуле без отдельного прохода на min/max и без сортировки каждой корзины по отдельности, добиваясь среднего O(n) буквально за один проход по массиву.

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

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

Число корзин - явный параметр настройки, не деталь реализации: слишком мало корзин (например, √n вместо n) сохраняет асимптотику деградировавшей до O(n^1.5) даже на идеально равномерных данных (см. разбор в разделе «Как это работает»), а слишком много корзин увеличивает накладные расходы на создание и обход почти пустых массивов.

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

На маленьких массивах (n < 50-100) накладные расходы на создание корзин и последующую конкатенацию обычно перевешивают выигрыш - обычный insertion sort или встроенная сортировка языка работает быстрее без лишнего шага группировки.

Если распределение данных неизвестно заранее и не может быть гарантировано равномерным, безопаснее выбрать алгоритм с гарантированным средним случаем независимо от входа (quicksort, Timsort) - ошибочное допущение равномерности не просто замедляет работу, а способно выродить сортировку до O(n²), как показано в примере с перекошенным распределением выше.

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

GPU-параллельная блочная сортировка - исследования по сортировке на CUDA часто используют bucket sort как первый этап: каждая корзина назначается отдельному thread block и сортируется независимо, поскольку GPU-архитектура хорошо подходит именно под такое разбиение на изолированные подзадачи.

Apache Spark's repartitionByRange разбивает строки датафрейма на партиции по диапазонам значений ключа перед параллельной сортировкой каждой партиции - тот же принцип «разложить по диапазону, затем отсортировать порознь», что и в bucket sort.

Распределённые SQL-базы данных (CockroachDB, Google Spanner) делят пространство ключей таблицы на диапазоны и закрепляют каждый диапазон за отдельным узлом кластера - распределение по диапазону значений, а не по хэшу, концептуально то же самое разбиение на корзины.

MSD-вариант поразрядной сортировки (most-significant-digit radix sort) можно рассматривать как специализированную блочную сортировку с ровно 256 корзинами на каждый байт ключа - в высокопроизводительных библиотеках сортировки для GPU и SIMD эти два алгоритма нередко делят общий код распределения по корзинам.

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

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

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

• Обработка больших объёмов числовых измерений (научные вычисления, финансовые тики) с заранее известным диапазоном значений и равномерным разбросом.
• Распределённые системы обработки данных (аналог MapReduce) используют идею блочной сортировки: данные «разбрасываются» по узлам-корзинам по диапазону ключа, каждый узел сортирует свою часть независимо.