Sorting Network (Batcher's)

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

Пререквизит:Big O Нотация

Лучший: O(n log² n)Средний: O(n log² n)Худший: O(n log² n)Память: O(n)

Проблема

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

Решение

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

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

В коде параметр r функции oddEvenMerge - это не индекс, а шаг (расстояние) между сравниваемыми элементами: на входе в рекурсию r = 1 (сравниваются соседи), а на каждом уровне рекурсии он удваивается (m = r * 2). Это отражает саму суть нечётно-чётного слияния - сначала объединяются элементы, отстоящие друг от друга на 1 позицию (условно «нечётные» и «чётные» подпоследовательности), затем на 2, затем на 4 и так далее, пока шаг не станет достаточно большим, чтобы одного сравнения хватило.

База рекурсии - строки 22-23 (JS) - срабатывает, когда m >= len: дальше дробить нечётно-чётным разбиением уже некуда, и функция просто сравнивает и при необходимости меняет местами единственную оставшуюся пару a[lo]/a[lo + r]. Рекурсивный случай (строки 16-21) сначала рекурсивно сливает «чётную» подпоследовательность (oddEvenMerge(lo, len, m)) и «нечётную» (oddEvenMerge(lo + r, len, m)), а затем один проход for (строка 19) сравнивает пары с шагом r между уже слитыми подпоследовательностями - это и есть тот самый «финальный проход», исправляющий оставшиеся нарушения.

Сравним с битонической сортировкой: та строит битоническую последовательность (сначала возрастающую, потом убывающую) и «расчёсывает» её половинным сравнением элементов, отстоящих на n/2. Сеть Батчера действует иначе - она не требует битонической формы входа вообще, а полагается на то, что обе половины уже монотонно отсортированы обычным (не битоническим) образом, и просто аккуратно чередует слияние по чётности и коррекцию соседей.

Пример на n = 4: пусть обе половины [1, 3] и [2, 4] уже отсортированы. Нечётно-чётное слияние сравнивает чётные позиции (1 и 2 → без обмена) и нечётные (3 и 4 → без обмена) отдельно, затем финальный проход сравнивает соседей 3 и 2 (индексы 1 и 2 объединённого массива [1, 3, 2, 4]) и меняет их местами - результат [1, 2, 3, 4]. Всего на этом уровне потребовалось 3 сравнения вместо 6 у наивного попарного сравнения всех элементов.

Глубина сети - O(log² n) уровней, тот же порядок, что и у битонической сортировки: oddEvenMergeSort (строки 27-34) даёт log n уровней разбиения пополам, а каждый вызов oddEvenMerge на своём уровне сам рекурсивно углубляется ещё на log n шагов через удвоение r. При n = 1 000 000: log₂(1 000 000) ≈ 20, значит глубина сети около 20 × 20 = 400 уровней сравнений - большая, но фиксированная и предсказуемая величина, не зависящая от порядка входных данных.

Как и в битонической сортировке, массив дополняется до ближайшей степени двойки «часовыми» (sentinel, строка 7 JS) - значением заведомо больше любого элемента входа, - потому что рекурсивное деление пополам с сохранением инварианта чётности требует одинаковой длины на каждом уровне. После завершения сети дополнение просто отбрасывается (a.slice(0, n), строка 37).

Сеть Батчера появилась в той же статье 1968 года Кеннета Батчера «Sorting Networks and Their Applications», что и битоническая сортировка - обе конструкции решали одну задачу (сортировка на параллельном оборудовании без зависимости от данных), но с разными компромиссами по числу компараторов и простоте построения индексов.

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

Та же ниша, что и битоническая сортировка - параллельное и аппаратное исполнение (FPGA/ASIC, SIMD), где важна статическая, известная заранее последовательность сравнений, но с чуть меньшим числом компараторов при том же O(n log² n).

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

Не подходит, если важно общее число сравнений на последовательном процессоре - обычная сортировка слиянием с её O(n log n) и адаптивным числом сравнений выигрывает у фиксированной сети O(n log² n).

Стоит выбрать сеть Батчера вместо битонической, когда число физических компараторов - ограниченный ресурс (площадь кристалла в ASIC), поскольку она использует их меньше при той же глубине.

Как вторая точка сравнения при изучении сортирующих сетей - показывает, что задача «зафиксировать сеть сравнений заранее» решается не единственным способом, а целым семейством конструкций с разными компромиссами.

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

Кеннет Батчер, 1968 - статья "Sorting Networks and Their Applications" (AFIPS Spring Joint Computer Conference), где одновременно представлены и битоническая сортировка, и нечётно-чётная сеть слияния.

Учебники по параллельным алгоритмам (например, "Introduction to Parallel Computing" Grama et al.) разбирают сеть Батчера как канонический пример сети слияния с меньшим числом компараторов, чем у битонической.

Модули аппаратной сортировки на FPGA (часто в конвейерах обработки сетевых пакетов и баз данных на кристалле) реализуют именно нечётно-чётные сети слияния ради экономии логических элементов.

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

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

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

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

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