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

Рис. 11.2. Пример выполнения нисходящего нечетночетного слияния Бэтчера
Чтобы слить ключи A G I N O R S T с ключами A E E L M P X Y, мы начинаем с выполнения операции обратного тасования, порождающей две независимые задачи слияния наполовину меньших массивов (показаны во второй строке): теперь нужно слить A I O S с A E M X (в первой половине массива) и G N R T с E L P Y (во второй половине массива). После рекурсивного решения этих подзадач мы тасуем результирующие массивы, (показаны в предпоследней строке) и завершаем сортировку выполнением операций сравнения-обмена E с A, G с E, L с I, N с M, P с O, R с S и T с X.
Почему данный метод сортирует все возможные перестановки входных данных? Ответ на этот вопрос далеко не очевиден; классическое доказательство этого факта является косвенным и зависящим от общих характеристик неадаптивных программ сортировки.
Лемма 11.1. (Принцип нулей и единиц.) Если неадаптивная программа выдает отсортированный результат для входных данных, состоящих только из 0 и 1, то она праавильно выполнит сортировку входных данных с произвольными ключами.
См. упражнение 11.7. 
Лемма 11.2. Нечетно-четное слияние Бэтчера (программа 11.2) правильно выполняет слияние.
Используя принцип нулей и единиц, достаточно проверить, правильно ли выполняются слияния, когда входными ключами являются только нули и единицы. Предположим, что в первом подфай-ле содержатся i нулей, а во втором подфайле - j нулей. Для доказательства этого свойства нужно рассмотреть четыре случая, в зависимости от того, являются ли i и j четными или нечетными числами. Если обе они четные, то одна подзадача слияния выполняется над файлом с i/2 нулями, а другая - над файлом с j/2 нулями, и вместе получается (i + j) / 2 нулей. После тасования получится сортированный файл типа 0-1.
Файл типа 0-1 также будет отсортирован после тасования и в тех случаях, когда i четно, а j нечетно, и когда i нечетно, а j четно. Но если и i, и j нечетны, то в завершение тасуется файл, содержащий (i + j) / 2 + 1 нулей, с файлом, содержащим (i + j) / 2 - 1 нулей, поэтому полученный после тасования файл содержит i + j - 1 нулей, единицу, ноль и N- i -j - 1 единиц (см. рис. 11.3), и на завершающем этапе один из компараторов заканчивает сортировку. 
На самом деле нет необходимости тасовать данные. И действительно, программы 11.2 и 8.3 могут быть переделаны таким образом, чтобы получилась линейная сортирующая программа для любого N - для этого необходимо скорректировать реализации compexch и shuffle, чтобы они поддерживали индексы и косвенный доступ к данным (см. упражнение 11.12). Либо можно сделать так, чтобы программа генерировала последовательность команд сравнения-обмена, которую можно применить к исходному входному файлу (см. упражнение 11.13). Эти приемы можно использовать для любого неадаптивного метода сортировки, переупорядочивающего данные при помощи операций обмена, тасования или им подобных. Что касается слияния Бэтчера, то структура этого алгоритма настолько проста, что, как будет показано в разделе 11.2, для него можно непосредственно разработать восходящую реализацию.