Чётно-нечётная сортировка слиянием

Урок про сортировку, где каждый процессор общается только с соседями — удобно для линейных топологий.

Чётно-нечётная транспозиционная сортировка — параллельный аналог пузырьковой: на чётных фазах сравниваются пары (0,1),(2,3),..., на нечётных — (1,2),(3,4),..., и так n фаз.

Идея фаз

Расставим элементы в ряд. На чётной фазе одновременно сравниваем и при необходимости меняем местами пары, начинающиеся с чётных индексов: (a0,a1), (a2,a3), (a4,a5)... На нечётной фазе — пары с нечётных индексов: (a1,a2), (a3,a4)... Чередуем фазы. За n фаз массив гарантированно отсортирован. Прелесть в том, что каждое сравнение локально — между соседями, поэтому алгоритм идеален для процессоров, выстроенных в линию или кольцо, где общение возможно только с соседом.

def odd_even_sort(a):
    a = a[:]
    n = len(a)
    for phase in range(n):
        start = phase % 2                  # 0 = чётная, 1 = нечётная
        for i in range(start, n - 1, 2):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
        label = "нечёт" if start else "чёт "
        print(f"фаза {phase} ({label}): {a}")
    return a

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

Вывод:

вход: [5, 2, 8, 1, 9, 3, 7, 4]
фаза 0 (чёт ): [2, 5, 1, 8, 3, 9, 4, 7]
фаза 1 (нечёт): [2, 1, 5, 3, 8, 4, 9, 7]
фаза 2 (чёт ): [1, 2, 3, 5, 4, 8, 7, 9]
фаза 3 (нечёт): [1, 2, 3, 4, 5, 7, 8, 9]
фаза 4 (чёт ): [1, 2, 3, 4, 5, 7, 8, 9]
фаза 5 (нечёт): [1, 2, 3, 4, 5, 7, 8, 9]
фаза 6 (чёт ): [1, 2, 3, 4, 5, 7, 8, 9]
фаза 7 (нечёт): [1, 2, 3, 4, 5, 7, 8, 9]
итог: [1, 2, 3, 4, 5, 7, 8, 9]

Уже после фазы 3 массив отсортирован, но алгоритм для гарантии прогоняет все n фаз. Внутри одной фазы все сравнения независимы (пары не пересекаются), поэтому идут одновременно на разных процессорах.

Анализ

n фаз, в каждой до n/2 параллельных сравнений. Глубина — O(n) шагов, работа — O(n²) сравнений. Это хуже битонической по асимптотике, зато алгоритм предельно прост и требует лишь локальной связи. Версия «слиянием» (odd-even merge) уменьшает глубину до O(log²n), сливая отсортированные подмассивы вместо одиночных элементов — это уже сортировочная сеть Бэтчера, родственная битонической.

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

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

Этот алгоритм поучителен ещё и тем, что показывает связь между топологией железа и выбором алгоритма. Если процессоры соединены в линию и каждый умеет говорить лишь с соседями, то алгоритм, требующий обмена с далёкими процессорами, придётся реализовывать через цепочку пересылок — медленно. Чётно-нечётная сортировка же изначально спроектирована под локальность: всё общение происходит между непосредственными соседями. Урок шире сортировки: проектируя параллельный алгоритм, всегда держите в уме, как соединены вычислители, ведь стоимость «дальней» коммуникации может оказаться решающей.

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

• Прервать алгоритм раньше n фаз «потому что уже отсортировано» — без проверки это рискованно, гарантия даёт именно полный набор фаз.
• Сравнивать пересекающиеся пары в одной фазе — нарушится независимость и параллельность.
• Ждать хорошей асимптотики — базовая версия делает O(n²) работы.

Итоги

• Чётно-нечётная сортировка чередует фазы сравнения соседних пар, всего n фаз.
• Внутри фазы пары не пересекаются — сравнения независимы и параллельны.
• Нужна лишь локальная связь между соседями — удобно для линеек/решёток процессоров.