Сортировка Батчера по нечетному и четному слиянию [1] — это общая конструкция, разработанная Кеном Батчером для сортировки сетей размером O( n (log n ) 2 ) и глубиной O((log n ) 2 ), где n — количество сортируемых элементов. Хотя она не является асимптотически оптимальной, в 1998 году Кнут пришел к выводу относительно сети AKS , что «метод Батчера намного лучше, если только n не превышает общую емкость памяти всех компьютеров на Земле!» [2]
Он популяризирован во второй книге GPU Gems [3] как простой способ выполнения достаточно эффективной сортировки на оборудовании для обработки графики.
Возможны различные рекурсивные и итерационные схемы для вычисления индексов сравниваемых и сортируемых элементов. Это один из итерационных методов генерации индексов для сортировки n элементов:
# примечание: входная последовательность индексируется от 0 до (n-1)для p = 1, 2, 4, 8, ... # пока p < n для k = p, p/2, p/4, p/8, ... # пока k >= 1 для j = mod(k,p) до (n-1-k) с размером шага 2k для i = 0 до min(k-1, njk-1) с шагом 1 если пол((i+j) / (p*2)) == пол((i+j+k) / (p*2)) сравнить и отсортировать элементы (i+j) и (i+j+k)Также возможен нерекурсивный расчет индекса узла-партнера. [4]