Сортировка дозатора сливается с объединением Бэтчера.
Чтобы объединить два массива A и B, объединение Batcher объединяет A в прямом порядке с B в обратном порядке, создавая битномический массив. Затем он применяет битоновую сортировку Бэтчера.
Битчерский сорт Бэтчера - двоюродный брат быстрой сортировки. Он делит массив на две половины, делает некоторые свопы, чтобы гарантировать, что ни один элемент в первой половине больше, чем элемент во втором, и рекурсивно сортирует половинки.
Массив битнитовый, если его можно поворачивать так, чтобы его элементы увеличивались, а затем уменьшались. По принципу «нуль-1» для забытых сортов достаточно доказать правильность на нулевых входах, и мы сделаем это предположение сейчас. Возможности
0^a 1^b 0^c = 0 ... a copies ... 0 1 ... b copies ... 1 0 ... c copies ... 0 (rotate right by c positions)
и
1^a 0^b 1^c (rotate left by a positions)
где а, б, в неотрицательные целые числа. Bitonic рода первый расщепляет этот массив на две равные половины размера А и B. Есть несколько возможностей:
A = 0^w
B = 1^x 0^y 1^z
или
A = 0^w 1^x
B = 1^y 0^z
или
A = 0^w 1^x 0^y
B = 1^z
или три других с нулем и одним взаимозаменяемым. Догадка Бэтчера заключается в том, что, применяя компаратор для всех i к A [i], B [i], либо A - все нули, и B - битноидный, либо A - битонический, а B - все. В любом случае, предварительное условие для рекурсивных сортов выполняется.
Единственные нетривиальные случаи
A = 0^w 1^x
B = 1^y 0^z
и его дополнение. Если ш> = у, то A, B стал
A = 0^(w+x)
B = 1^y 0^(w-y) 1^x
так А все нули и В bitonic. Если ж < у, то
A = 0^w 1^(y-w) 0^z
B = 1^(y+z)
так Б все из них, а А bitonic. Если мы рекурсивно сортируем A и B, то их конкатенация является отсортированным массивом.