Решение этих рекуррентных соотношений (см. упр. 2) показывает, что обш,ий объем информации, считываемой с ленты в течение фаз внешнего разделения, в среднем равен 6AlnJV + 0{N) при N со. Мы также знаем из формулы 5.2.2-(25), что среднее число фаз внутренней сортировки будет равно 2(Л + 1)/(М + 2) - 1.

Если применить этот анализ к примеру со 100,000 записями, рассмотренному в разделе 5.4.6, причем полагая, что в нашем распоряжении имеются буфера по 25,000 символов и время сортировки подфайла из п < М = 1000 записей равно 2пСшт, то получится среднее время сортировки, приблизительно равное 103 мин (включая, как на диаграмме А, окончательную перемотку). Итак, метод быстрой сортировки в среднем не плох, но, конечно, в наихудшем случае он ужасен и уступает даже методу пузырька, обсуждавшемуся выше. Тем не менее рандомизация сделает наихудший случай весьма маловероятным.

Поразрядная сортировка. Обменную поразрядную сортировку (алгоритм 5.2.2R) можно аналогичным образом приспособить для сортировки с двумя лентами, так как этот метод очень похож на быструю сортировку. В качестве трюка, который позволяет применить оба эти метода, можно воспользоваться идеей многократного чтения файла - тем, чего мы никогда не делали в предыдущих алгоритмах для работы с лентами.

Тот же трюк позволяет осуществить обычную поразрядную сортировку на двух лентах "сначала по младшей цифре" Имея исходные данные на Т1, копируем на Т2 все записи, ключ которых в двоичной системе оканчивается нулем. Затем, после перемотки Т1, читаем ее вновь, копируя записи с ключами, оканчивающимися единицей. Теперь перематываются обе ленты и выполняется аналогичная пара проходов, но с заменой Т1 лентой Т2 и использованием предпоследней двоичной цифры. В этот момент на Т1 будут содержаться все записи с ключами (.. .00)2, за которыми следуют записи с ключами (... 01)2, затем - (... 10)2, затем - (... 11)2-Если ключи имеют размер b бит, то, чтобы завершить сортировку, потребуется только 2Ь проходов по всему файлу.

Подобную поразрядную сортировку можно применять только к старшим b бит ключа для некоторого разумно выбранного числа Ь; таким образом, если ключи были равномерно распределены, число инверсий уменьшится примерно в 2* раз. После этого несколько проходов Р-путевой сортировки методом пузырька позволят завершить работу.

Новый, но несколько более сложный подход к распределяющей сортировке с двумя лентами предложили А. И. Никитин и Л. И. Шолмов [Кибернетика 2,6 (1966), 79-84]. Имеются счетчики числа ключей (по одному на каждую возможную конфигурацию старших битов), на основе которых строятся искусственные ключи Ki, К.2,..., Км так, чтобы для каждого г число действительных ключей, лежащих между Ki и Kj+i, находилось в заранее заданном диапазоне между Pi и Рг. Таким образом, М лежит между IN/P2] и \N/Pi]. Если счетчики старших битов не дают достаточной информации для определения таких ki , «2,..., км, то делается еще один или более проходов для подсчета частоты конфигураций менее значащих битов при некоторых конфигурациях старших битов. После того как таблица искусственных ключей построена, 2"lgM] проходов будет достаточно для завершения сортировки. (Данный метод требует объема оперативной памяти, пропорционального Л, и поэтому не может использоваться для внешней сортировки при N оо.

На практике мы не станем применять его для файлов на нескольких бобинах, и, следовательно, М будет сравнительно невелико, так что таблица искусственных ключей легко поместится в памяти.)

Имитация дополнительных лент. Ф. К. Хенни (F. С. Hennie) и Р. Э. Стирнз (R. Е. Stearns) изобрели общий метод имитации к лент всего на двух лентах, причем таким образом, что требуемое суммарное перемещение ленты возрастает всего лишь в O(logL) раз, где L - максимальное расстояние, которое нужно пройти на любой одной ленте [JACM 13 (1966), 533-546]. Их построение в случае сортировки можно слегка упростить, что и сделано в следующем методе, предложенном Р. М. Карпом.

Будем имитировать обычное сбалансированное слияние на четырех лентах, используя две ленты: Т1 и Т2. На первой из них (т. е. на Т1) содержимое имитируемых лент хранится так, как изображено на рис. 86. Представим себе, что данные записаны на четырех "дорожках" по одной для каждой имитируемой ленты. (В действительности лента не имеет таких дорожек. Мы просто будем считывать блоки 1, 5, 9, 13, ... , как дорожку 1, блоки 2, 6, 10, 14, ... , как дорожку 2, и т. д.) Другая лента (Т2) используется только для вспомогательного хранения, чтобы помочь в выполнении перестановок на Т1.

Зона О Зона 1

Зона 2

Зона 3

:. 86. Разбивка ленты Т1 в конструкции Хенни-Стирнза (непустые зоны заштрихованы).

Блоки на каждой дорожке разделяются на зоны, содержащие соответственно 1, 2, 4, 8, ..., 2*, ... блоков. Зона к на каждой дорожке либо заполнена точно 2* блоками данных, либо пуста. Например, на рис. 86 на дорожке 1 данные содержатся в зонах 1 и 3, на-дорожке 2 - в зонах О, 1 и 2, на дорожке 3 - в зонах О и 2, на дорожке 4 - в зоне 1, а все остальные зоны пусты.

Предположим, что мы выполняем слияние данных с дорожек 1 и 2 на дорожку 3. В оперативной памяти находятся два буфера, используемые двухпутевым слиянием для ввода, а также третий буфер - для вывода. Когда буфер ввода для дорожки 1 станет пустым, можно заполнить его следующим образом: найти первую непустую зону дорожки 1, скажем зону к, и скопировать ее первый блок в буфер ввода, затем скопировать остальные 2* - 1 блоков данных на Т2 и переместить их в зоны О, 1,

А: -1 дорожки 1. (Теперь зоны О, 1, А: -1 заполнены, зона к пуста.) Аналогичная процедура используется, чтобы заполнить буфер ввода для дорожки 2, как только он станет пустым. Когда буфер вывода подготовлен для записи на дорожку 3, мы обращаем этот процесс, т. е. просматриваем Т1, пока не найдется первая пустая зона на дорожке 3, скажем зона А:, и в то же время копируем данные из зон О, 1, ..., к-1 на Т2. Данные на Т2, к которым присоединяется содержимое буфера вывода, используются теперь для заполнения зоны к на дорожке 3.

Для этой процедуры необходимо уметь выполнять запись в середину ленты Т1, не разрушая последуюш,ую информацию. Как и в случае осциллирующей сортировки с прямым чтением (раздел 5.4.5), можно без опасений выполнять это действие, если принять меры предосторожности.

Поскольку просмотр до зоны к осуществляется только один раз за каждые 2* шагов, то, чтобы переписать 2 - 1 блоков с дорожки 1 в память, потребуется переместить ленту на Xlo<fc<i "" • с 2* = cl2, где с - некоторая константа. Таким образом, каждый проход слияния требует 0(AlogA) шагов. Поскольку в сбалансированном слиянии имеется O(logA) проходов, общее время работы будет составлять 0{N{logN)), что аси.мптотически значительно лучше, чем наихудший случай для быстрой сортировки.

На самом же деле этот метод оказывается почти бесполезным, если применяется для сортировки 100,000 записей из примера раздела 5.4.6, поскольку информация, которая должна размещаться на ленте Т1, не поместится на одной бобине ленты. И даже если мы пренебрежем этим фактом и будем исходить из самых оптимистических предположений относительно совмещения чтения/записи/вычислений, относительно длин междублочных промежутков и т. д., то найдем, что для вьшолнения сортировки потребуется около 37 ч! Итак, этот метод представляет чисто академический интерес: константа в О (Л(log Л) слишком велика, чтобы метод можно было эффективно использовать при реальных значениях Л.

Одноленточная сортировка. Можно ли обойтись всего одной лентой? Нетрудно видеть, что сортировку методом пузырька Р-го порядка можно преобразовать в одноленточную сортировку, но результат будет ужасен. Г. Б. Демут [Ph. D. thesis (Stanford University, 1956), 85] сделал вывод, что в компьютере с ограниченной оперативной памятью после просмотра ограниченного участка ленты нельзя уменьшить число инверсий перестановки больше чем на ограниченную величину. Следовательно, любой алгоритм сортировки с одной лентой потребует в среднем не более чем Л единиц времени (где d - некоторая положительная константа, зависящая от конфигурации компьютера).

Р. М. Карп нашел очень интересный подход к исследованию этой задачи, обнаружив то, что, по существу, является оптимальным способо.м сортировки с одной лентой. При анализе алгоритма Карпа удобно следующим образом переформулировать задачу: как быстрее всего перевезти людей между этажами, если работает только один лифт? [См. Combinatorial igoritiims, edited by Randall Rustin (Algorithmics Press, 1972), 17-21.]

Рассмотрим здание с n этажами; помещение каждого этажа рассчитано на Ь человек. В этом здании нет ни окон, ни дверей, ни лестниц, но есть лифт, который может останавливаться на любом этаже. В здании находятся Ьп человек, и ровно Ь из них хотят попасть на свой этаж. В лифт вмещается самое большее т человек, и он затрачивает одну единицу времени для перемещения с этажа i на этаж г -Ь 1. Как найти самый быстрый способ перемещения всех людей на нужные этажи, если требуется, чтобы лифт начал и закончил свое движение на первом этаже?

Нетрудно заметить связь между этой задачей и одноленточной сортировкой: люди - это записи, здание - лента, этажи - отдельные блоки на ленте, а лифт - оперативная память компьютера. Действиям программ для компьютера свойственна большая гибкость, чем действиям лифтера (программа может, напри-