Битоническая сортировка: сортировочная сеть

Урок про сортировку, у которой расписание сравнений известно заранее и не зависит от данных.

Сортировочная сеть — фиксированная последовательность операций «сравни-и-обменяй» (compare-and-swap), которая сортирует любой вход. Битоническая сортировка — самая известная такая сеть, удобная для параллельного железа.

Почему обычная сортировка плохо параллелится

В quicksort выбор опорного элемента и точка разбиения зависят от данных — заранее не известно, какой кусок какого размера достанется. Это ветвление и дисбаланс. А для GPU и аппаратных сетей идеален алгоритм, где расписание сравнений фиксировано: какие пары сравнивать и в каком порядке — известно до запуска, одинаково для любого входа. Тогда тысячи компараторов работают синхронно без ветвлений. Битоническая сортировка — ровно такая.

Битонная последовательность

Последовательность называется битонной, если сначала возрастает, потом убывает (или это циклический сдвиг такой). Ключевая операция — «битонное слияние»: битонную последовательность из n элементов за log n шагов превращают в отсортированную. Алгоритм рекурсивно строит битонные последовательности (сортируя половины в разных направлениях), а потом сливает их.

def bitonic_sort(a):
    a = a[:]
    n = len(a)
    def cas(arr, i, j, up):           # compare-and-swap
        if (up and arr[i] > arr[j]) or (not up and arr[i] < arr[j]):
            arr[i], arr[j] = arr[j], arr[i]
    def merge(arr, lo, cnt, up):
        if cnt > 1:
            k = cnt // 2
            for i in range(lo, lo + k):
                cas(arr, i, i + k, up)
            merge(arr, lo, k, up)
            merge(arr, lo + k, k, up)
    def sort(arr, lo, cnt, up):
        if cnt > 1:
            k = cnt // 2
            sort(arr, lo, k, True)        # левую — по возрастанию
            sort(arr, lo + k, k, False)   # правую — по убыванию -> битонно
            merge(arr, lo, cnt, up)
    sort(a, 0, n, True)
    return a

data = [3, 7, 4, 8, 6, 2, 1, 5]
print("вход:", data)
print("итог:", bitonic_sort(data))

Вывод:

вход: [3, 7, 4, 8, 6, 2, 1, 5]
итог: [1, 2, 3, 4, 5, 6, 7, 8]

Сколько шагов

Битоническая сеть для n элементов (n — степень двойки) имеет log₂(n)·(log₂(n)+1)/2 стадий, и на каждой стадии выполняется n/2 сравнений одновременно. Для n=8 это 6 стадий по 4 компаратора. Глубина — O(log²n), что больше теоретического оптимума O(log n), зато расписание полностью предсказуемо и не зависит от данных — бесценно для аппаратной реализации.

Стадии для n=8 (каждая стадия = 4 параллельных компаратора):
log2(8) = 3  ->  стадий = 3*4/2 = 6
на каждой стадии: n/2 = 4 сравнения сразу

Как работает под капотом

На GPU каждый поток отвечает за один компаратор стадии. Все потоки стадии срабатывают одновременно, затем барьер, затем следующая стадия. Поскольку индексы пар вычисляются по номеру стадии (а не по данным), нет ветвлений по значениям — идеально для SIMT-архитектуры. Битоническую сортировку используют там, где важна предсказуемость: сортировка в шейдерах, аппаратные сети, сортировка фиксированного размера.

Битоническая сортировка показывает важный принцип: для параллельного железа предсказуемость иногда ценнее асимптотики. Её O(log²n) глубина хуже теоретического оптимума O(log n), и по числу сравнений она проигрывает обычной сортировке. Тем не менее на GPU она часто быстрее «лучших» алгоритмов — просто потому, что её расписание не содержит ветвлений, не зависит от данных и идеально ложится на синхронное исполнение warp'ов. Это общий мотив параллельного мира: алгоритм, который на бумаге делает больше операций, на реальной параллельной машине может выиграть, если эти операции регулярны и не требуют непредсказуемой координации.

Частые ошибки

• Применять к массиву не степени двойки без дополнения — сеть рассчитана на 2^k элементов.
• Ждать глубины O(log n) — у битонической сети O(log²n), она быстра по предсказуемости, а не по асимптотике.
• Путать направление слияния (up/down) в рекурсии — половины должны сортироваться в разные стороны.

Итоги

• Битоническая сортировка — сеть с фиксированным, не зависящим от данных расписанием сравнений.
• Глубина O(log²n), на каждой стадии n/2 параллельных компараторов.
• Идеальна для GPU и аппаратуры за счёт отсутствия ветвлений по данным.