Специальные методы сортировки a

Рис. 11.5. Сети нечетно-четного слияния Бэтчера
Показанные на этом рисунке различные представления сетей на четыре (вверху), восемь (в центре) и 16 (внизу) линий демонстрируют рекурсивную структуру, на которой основаны сети. Слева показаны непосредственные представления построения сети размера N с помощью двух копий сетей размера N/2 (одна для линий с четными номерами, другая для линий с нечетными номерами) плюс каскад компараторов между линиями 1 и 2, 3 и 4, 5 и 6 и т.д. Справа показаны более простые сети, полученные из сетей, изображенных слева, путем группирования компараторов одинаковой длины. Такое группирование возможно потому, что компараторы на нечетных линиях можно перемещать независимо от компараторов на нечетных линиях.
Программа 11.3. Нечетно-четное слияние Бэтчера (нерекурсивная версия)
Данная реализация нечетно-четного слияния Бэтчера (в которой предполагается, что размер файла N является степенью 2) компактна, но непонятна. Понять, как она выполняет слияние, можно, сравнив ее с рекурсивной версией (см. программу 11.2 и рис. 11.5). Она совершает слияние за lgN проходов, состоящих из единообразных и независимых инструкций сравнения-обмена.
template
void merge(Item a[], int l, int m, int r)
{ int N = r-l+1; // предполагается,
// что N/2 равно m-l+1
for (int k = N/2; k > 0; k /= 2)
for (int j = k % (N/2); j+k < N; j += k+k)
for (int i = 0; i < k; i++)
compexch(a[l+j+i], a[l+j+i+k]);
}
Для создания сливающей сети размера N мы воспользуемся двумя копиями сети размером N/2: одна для линий с четными номерами, а другая - с нечетными. Поскольку эти два множества компараторов не пересекаются, их можно распределить таким образом, чтобы обе сети чередовались. И в завершение мы расставим компараторы между линиями 1 и 2, 3 и 4 и т.д. Чередование нечетных и четных линий заменяет идеальное тасование из программы 11.2. Доказательство того, что эти сети выполняют слияние правильно, аналогично доказательствам свойств 11.1 и 11.2 с помощью принципа нулей и единиц. На рис. 11.6 показан пример выполнения такого слияния.