Bitonic Sort

Проблема

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

Решение

Массив (дополненный до размера, равного степени двойки) рекурсивно делится на две половины: левая сортируется по возрастанию, правая - по убыванию. Вместе они образуют битоническую последовательность (сначала растёт, потом падает). Такую последовательность можно слить в отсортированный порядок с помощью «битонического слияния»: сравнить и, если нужно, поменять местами каждый элемент первой половины с соответствующим элементом второй половины, затем рекурсивно слить каждую половину так же. Ключевое свойство: результат такого слияния всегда правильно отсортирован, а пары сравнений полностью фиксированы заранее - это и есть сеть сравнений.

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

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

Построение идёт снизу вверх, блоками возрастающего размера. Для блока из 2 элементов один сортируется по возрастанию, второй - по убыванию: вместе они уже битоническая пара. Для блока из 4 - две готовые битонические пары сортируются в противоположных направлениях и снова образуют битоническую последовательность вдвое длиннее. Так на каждом уровне размер блока удваивается, пока не охватит весь массив.

Слияние битонической последовательности длиной cnt работает так: сравнить элемент i первой половины с элементом i + k второй (k = cnt / 2) и поменять местами при необходимости. После этого шага - и это ключевое свойство сети - все элементы первой половины меньше или равны всем элементам второй (для возрастающего направления), а обе половины сами остаются битоническими последовательностями. Значит, их можно слить рекурсивно тем же способом, пока размер блока не станет равным 1.

Почему это вообще корректно для произвольных чисел, а не только для наглядного примера? Здесь помогает классический приём теории сетей сравнений - принцип ноля-единицы (zero-one principle): если сеть компараторов правильно сортирует любую последовательность из нулей и единиц, она правильно сортирует и любую последовательность произвольных чисел. Доказательство для 0/1-последовательностей проще, потому что таких последовательностей конечное число - его придумал Кен Бэтчер в 1968 году вместе с самой сетью.

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

Дополнение до степени двойки - не случайность реализации, а прямое следствие того, как строится сеть: каждый уровень делит блок ровно пополам (k = cnt / 2), и это деление предполагается точным. Для произвольного n (например, 13) массив дополняют фиктивными sentinel-элементами, заведомо большими любого настоящего значения, до ближайшей степени двойки (16). После завершения сети эти элементы просто отбрасываются - они всегда оказываются в конце отсортированного результата.

Ключевое отличие от «обычных» быстрых алгоритмов - в том, что именно измеряет сложность. У merge sort и quicksort O(n log n) - это последовательная работа одного процессора. У битонической сети O(n log² n) - тоже последовательная работа, но при наличии n/2 параллельных компараторов реальное время выполнения сводится к глубине сети, O(log² n), потому что все сравнения одного уровня независимы друг от друга и выполняются одновременно. Именно эта параллельная глубина, а не общее число сравнений, делает сеть привлекательной для GPU и FPGA.

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

Параллельное оборудование - главная и практически единственная причина выбирать битоническую сортировку. На GPU-шейдерах, FPGA и SIMD-инструкциях важна не общая скорость на одном ядре, а предсказуемая, статическая последовательность операций без ветвлений по данным - именно это и даёт фиксированная сеть сравнений.

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

Обычный последовательный процессор - худший сценарий для битонической сортировки. Она делает O(n log² n) сравнений против O(n log n) у merge sort, то есть на однопоточном CPU почти всегда медленнее при большом n. Без параллельного железа выигрыш в предсказуемости не окупает лишние сравнения.

Три оси сравнения с соседями по классу: скорость на одном ядре - хуже quicksort и merge sort (лишний множитель log n). Параллельная глубина - лучше почти всех сравнительных сортировок, потому что merge sort имеет O(n) последовательных шагов слияния, а сеть - O(log² n). Предсказуемость - максимальная: пары сравнений известны до запуска, в отличие от quicksort, где выбор опорного элемента зависит от данных.

Данные переменного размера в рантайме - ситуация, где преимущество сети частично теряется. Дополнение до степени двойки означает, что при n=17 сеть фактически работает с 32 элементами, тратя сравнения на фиктивные sentinel-значения. При сильно нерегулярных размерах данных это может съедать заметную часть выигрыша от параллелизма.

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

Игровые движки - одна из самых заметных практических ниш. Битоническая сортировка через compute-шейдеры используется для сортировки частиц по глубине перед рендерингом прозрачности (order-independent transparency): без сортировки полупрозрачные частицы накладываются в неверном порядке и дают визуальные артефакты. Такой подход применяется в системах частиц Unreal Engine и Unity DOTS - счёт может идти на сотни тысяч частиц за кадр.

Историю сети задал один человек: в 1968 году Кен Бэтчер опубликовал статью «Sorting Networks and Their Applications», где представил и битоническую сеть, и родственную ей odd-even mergesort. Обе были придуманы для аппаратных сортирующих устройств задолго до появления современных GPU - идея «сравнения без ветвлений» родилась именно из ограничений железа 1960-х.

До появления современных GPU-библиотек сортировки (вроде Thrust для CUDA) программисты реализовывали сортировку на видеокартах через пиксельные шейдеры - в известной статье «Improved GPU Sorting» (GPU Gems 2, 2005) именно битоническая сеть использовалась как основа, потому что старые шейдерные конвейеры вообще не поддерживали условные переходы по данным.

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

При этом ни в одной массовой стандартной библиотеке для CPU (V8, CPython, Java) битоническая сортировка не применяется - там правят Timsort и introsort, потому что на одном ядре лишний множитель log n в сложности перевешивает предсказуемость. Битоническая сеть остаётся узкоспециализированным инструментом именно для параллельного и аппаратного мира, а не заменой универсальным алгоритмам.

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

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

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

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