Bitonic Sort

Ключевое понятие — битонная последовательность: последовательность, которая сначала монотонно возрастает, затем монотонно убывает (или является циклическим сдвигом такой последовательности) — например, [1, 4, 7, 9, 6, 3]. У битонной последовательности есть удобное свойство: сравнив и при необходимости поменяв местами элементы i и i+n/2 для всех i от 0 до n/2-1, получаются две новые битонные последовательности, причём каждый элемент первой половины меньше или равен каждому элементу второй половины (это называется bitonic merge). Применяя это рекурсивно, битонная последовательность любой длины сортируется за log₂(n) таких шагов.The key concept is a bitonic sequence: one that first increases monotonically, then decreases monotonically (or is a cyclic rotation of such a sequence) — e.g. [1, 4, 7, 9, 6, 3]. A bitonic sequence has a convenient property: comparing and swapping if needed elements i and i+n/2 for all i from 0 to n/2-1 produces two new bitonic sequences, with every element of the first half ≤ every element of the second half (this is called a bitonic merge). Applying this recursively, a bitonic sequence of any length sorts in log₂(n) such steps.

Оставшаяся часть алгоритма — превратить произвольную последовательность в битонную. Это делается тоже рекурсивно: если отсортировать первую половину массива по возрастанию, а вторую по убыванию (тем же алгоритмом, рекурсивно), результат — ровно битонная последовательность, к которой уже можно применить bitonic merge. Полная рекурсия даёт log₂(n) уровней слияния, каждый требующий O(n) сравнений — итого O(n log² n) сравнений, выполненных по фиксированной, не зависящей от данных схеме.The rest of the algorithm is turning an arbitrary sequence into a bitonic one. This is also done recursively: sorting the first half of the array ascending and the second half descending (with the same algorithm, recursively) produces exactly a bitonic sequence, to which bitonic merge can then be applied. The full recursion gives log₂(n) merge levels, each requiring O(n) comparisons — totaling O(n log² n) comparisons, executed on a fixed, data-independent schedule.

void compare_swap(std::vector<int>& a, int i, int j, bool ascending) {
    if ((ascending && a[i] > a[j]) || (!ascending && a[i] < a[j])) std::swap(a[i], a[j]);
}
void bitonic_merge(std::vector<int>& a, int lo, int cnt, bool ascending) {
    if (cnt <= 1) return;
    int k = cnt / 2;
    for (int i = lo; i < lo + k; ++i) compare_swap(a, i, i + k, ascending); // весь цикл — параллельно// the whole loop — parallel
    bitonic_merge(a, lo, k, ascending);
    bitonic_merge(a, lo + k, k, ascending);
}
void bitonic_sort(std::vector<int>& a, int lo, int cnt, bool ascending) {
    if (cnt <= 1) return;
    int k = cnt / 2;
    bitonic_sort(a, lo, k, true);       // левая половина по возрастанию// left half ascending
    bitonic_sort(a, lo + k, k, false);  // правая половина по убыванию → битонная целиком// right half descending → bitonic as a whole
    bitonic_merge(a, lo, cnt, ascending);
}

Схема компараторов вычислена заранее для n=8 и никогда не меняется от значений — шагая по ней, можно наблюдать, как одна и та же последовательность сравнений сортирует любой массив. Жёлтая пара — текущий компаратор, стрелка показывает направление (по возрастанию ↑ или по убыванию ↓).The comparator schedule is computed in advance for n=8 and never changes based on values — stepping through it shows how the same sequence of comparisons sorts any array. The yellow pair is the current comparator, the arrow shows the direction (ascending ↑ or descending ↓).

По общему числу сравнений bitonic sort хуже, чем quicksort или merge sort (O(n log² n) против O(n log n)) — на последовательном процессоре это чистый проигрыш. Но глубина схемы (число последовательных "уровней", которые нельзя выполнить параллельно) — всего O(log² n), в то время как у merge sort таких зависимых уровней тоже O(log n), но каждый уровень требует O(n) последовательной работы на одном ядре. При наличии n или n/2 параллельных исполнителей (ядра GPU, полосы SIMD, физические компараторы в ASIC) bitonic sort сортирует за O(log² n) *времени* — экспоненциально быстрее любого последовательного алгоритма сравнения, ценой большего суммарного числа операций, которые распределены по многим исполнителям одновременно.By total comparison count, bitonic sort is worse than quicksort or merge sort (O(n log² n) vs O(n log n)) — a clear loss on a sequential processor. But the schedule's depth (the number of sequential "levels" that can't run in parallel) is only O(log² n), while merge sort also has O(log n) dependent levels, but each level needs O(n) sequential work on a single core. Given n or n/2 parallel executors (GPU cores, SIMD lanes, physical comparators in an ASIC), bitonic sort sorts in O(log² n) *time* — exponentially faster than any sequential comparison algorithm, at the cost of a larger total operation count spread across many executors at once.

Требование "n — степень двойки" — не техническая деталь для удобства реализации, а прямое следствие того, как строится битонная последовательность через рекурсивное деление пополам; для произвольного n используют модификации (дополнение до степени двойки фиктивными "бесконечными" элементами, либо более сложные схемы вроде Batcher's odd-even mergesort — следующая статья, 2.2.1.14).The "n is a power of two" requirement isn't an implementation convenience but a direct consequence of how a bitonic sequence is built via recursive halving; for arbitrary n, modifications are used (padding to a power of two with dummy "infinite" elements, or more elaborate schemes like Batcher's odd-even mergesort — the next article, 2.2.1.14).