Сортировка Дозатора является слиянием с объединением Дозатора.
Чтобы объединить два массива A и B, слияние Batcher объединяет A в прямом порядке с B в обратном порядке, создавая битовый массив. Затем применяется битоническая сортировка Дозатора.
Битонный сорт Дозатора - двоюродный брат быстрой сортировки. Он делит массив на две половины, выполняет некоторые перестановки, чтобы убедиться, что ни один элемент в первой половине не больше элемента во второй, и рекурсивно сортирует половинки.
Массив является битоническим, если его можно вращать так, чтобы его элементы увеличивались, а затем уменьшались. По принципу «ноль один» для забывчивых сортов достаточно доказать правильность на входах «ноль один», и мы сделаем это предположение сейчас. Возможности
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)
где a, b, c - неотрицательные целые числа. Битонная сортировка сначала разбивает этот массив на две равные половины A и 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
и его дополнение. Если w> = y, то A, B становятся
A = 0^(w+x)
B = 1^y 0^(w-y) 1^x
поэтому A - все нули, а B - битонический. Если w
A = 0^w 1^(y-w) 0^z
B = 1^(y+z)
так что B это все единицы, а A битонический. Если мы рекурсивно отсортируем A и B, то их объединение будет отсортированным массивом.