2.2.1.14 — сортирующая сеть Бэтчера: та же цель, что у bitonic sort, другая схема слияния2.2.1.14 — Batcher's sorting network: the same goal as bitonic sort, a different merge schedule
Как и bitonic sort (2.2.1.13), это сортирующая сеть — фиксированная, не зависящая от данных схема компараторов той же глубины O(log² n). Отличие в том, как две отсортированные половины сливаются: вместо прямого сравнения "зеркальных" элементов, здесь отдельно сливаются элементы на чётных и нечётных позициях, а затем один финальный проход компараторов исправляет то немногое, что осталось не на своём месте.Like bitonic sort (2.2.1.13), this is a sorting network — a fixed, data-independent comparator schedule of the same O(log² n) depth. The difference is how two sorted halves are merged: instead of directly comparing "mirrored" elements, the elements at even and odd positions are merged separately, and then one final pass of comparators fixes the little that's left out of place.
Алгоритм Бэтчера (1968) решает ту же задачу, что и bitonic merge, но опирается на другое наблюдение: если взять две уже отсортированные последовательности длины n/2, отдельно слить их элементы на чётных позициях друг с другом (рекурсивно тем же способом) и отдельно — элементы на нечётных позициях, а затем перемешать результаты, то итоговая последовательность окажется "почти отсортирована" — каждый элемент находится не дальше чем на одну позицию от своего верного места. Это доказанный факт (лемма Бэтчера о нечётно-чётном слиянии), и он гарантирует, что единственный дополнительный проход компараторов вида (2i+1, 2i+2) для всех i исправляет все оставшиеся нарушения.Batcher's algorithm (1968) solves the same problem as bitonic merge, but relies on a different observation: taking two already-sorted sequences of length n/2, separately merging their even-position elements with each other (recursively, the same way) and separately their odd-position elements, then interleaving the results, yields a sequence that is "almost sorted" — every element is at most one position away from its correct spot. This is a proven fact (Batcher's odd-even merge lemma), and it guarantees that a single extra pass of comparators of the form (2i+1, 2i+2) for all i fixes every remaining violation.
разделение на чётные/нечётные подзадачи вместо прямого попарного сравнения половин — та же глубина, другая структураsplitting into even/odd subproblems instead of directly pairing the halves — same depth, different structure
void compare_swap(std::vector<int>& a, int i, int j) {
if (a[i] > a[j]) std::swap(a[i], a[j]);
}
// слить a[lo..lo+n) — два подмассива с шагом r, уже отсортированные внутри// merge a[lo..lo+n) — two subarrays with stride r, already sorted within
void odd_even_merge(std::vector<int>& a, int lo, int n, int r) {
int step = r * 2;
if (step < n) {
odd_even_merge(a, lo, n, step); // слить чётные позиции// merge even positions
odd_even_merge(a, lo + r, n, step); // слить нечётные позиции// merge odd positions
for (int i = lo + r; i + r < lo + n; i += step)
compare_swap(a, i, i + r); // финальный проход-коррекция// final correction pass
} else {
compare_swap(a, lo, lo + r);
}
}
void odd_even_merge_sort(std::vector<int>& a, int lo, int n) {
if (n <= 1) return;
int m = n / 2;
odd_even_merge_sort(a, lo, m);
odd_even_merge_sort(a, lo + m, m);
odd_even_merge(a, lo, n, 1);
}Схема компараторов для n=8 вычислена заранее — как и в bitonic sort, она не зависит от значений массива. Жёлтая пара — текущий компаратор.The comparator schedule for n=8 is computed in advance — as with bitonic sort, it doesn't depend on the array's values. The yellow pair is the current comparator.
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Асимптотически идентичен bitonic sort — O(n log² n) сравнений, глубина O(log² n), то же требование n = степень двойки. Число компараторов у odd-even mergesort немного меньше (константа лучше примерно в 2 раза), что имеет значение при реализации в физическом железе (ASIC/FPGA), где каждый компаратор — это реальная схема, занимающая площадь кристалла. С другой стороны, схема bitonic sort проще для понимания и реализации в софте (единая рекурсивная схема без специального различения чётных/нечётных индексов), поэтому в GPU-шейдерах чаще встречается именно bitonic sort, а odd-even mergesort — там, где важна минимизация числа физических элементов.Asymptotically identical to bitonic sort — O(n log² n) comparisons, O(log² n) depth, the same n = power-of-two requirement. Odd-even mergesort uses somewhat fewer comparators (roughly a 2x better constant), which matters when implementing in physical hardware (ASIC/FPGA), where each comparator is a real circuit occupying die area. On the other hand, bitonic sort's schedule is simpler to understand and implement in software (a single recursive scheme with no special-casing of even/odd indices), which is why GPU shaders more often use bitonic sort, while odd-even mergesort shows up where minimizing the physical element count matters.
Меньшее число компараторов по сравнению с bitonic sort напрямую переводится в меньшую площадь кристалла и энергопотребление — важный практический критерий выбора именно этой сети при проектировании специализированного железа.Fewer comparators than bitonic sort translates directly into less die area and power consumption — an important practical criterion for choosing this network specifically when designing specialized hardware.
Алгоритм Бэтчера 1968 года — один из первых формально проанализированных примеров параллельного алгоритма сортировки вообще, регулярно используемый как отправная точка при изучении теории сортирующих сетей и границ AKS-сети (следующий шаг в теории — сеть с глубиной O(log n), но с непрактично большой константой).Batcher's 1968 algorithm is one of the first formally analyzed examples of a parallel sorting algorithm at all, routinely used as the starting point when studying sorting-network theory and the bounds of the AKS network (the next step in the theory — a network with O(log n) depth but an impractically large constant).