равен dkdn-k (см. упр. 5.4.3-5) и можно показать, что в случае Т лент объем перемотки после двухпутевых слияний приблизительно равен

(2/(2Г-1))(1-со5(47г/(2Г-1)))

от всего файла. В нашем случае Т - Ъ, что составляет (1 - cos80°) я 0.184 от длины файла, и это происходит в 0.946 In 5 -Ь 0.796 - 2 случаях.

Пример 6. Сбалансированное слияние с обратным чтением. Оно напоминает пример 1, но значительная часть операций перемотки устраняется. Изменение направления обработки ленты от прямого к обратному вызывает некоторые задержки, но они несущественны. С вероятностью 1/2 перед последним проходом понадобится перемотка, поэтому можно взять тг = 1/(2Р).

Пример 7. Многофазное слияние с обратным чтением. Так как в этом случае выбор с замещением порождает серии, меняющие направление примерно через каждые Р раз, то следует заменить (3) другой формулой для 5. Достаточно хорошим приближением будет 5 = [Л(3-Ь 1/Р)/(6Р)] + 1 (см. упр. 5.4.1-24). Все время перемотки устраняется, и из табл. 5.4.2-1 следует, что а х 0.863, /3 я 0.921 - 2.

Пример 8. Каскадное слияние с обратным чтением. Из табл. 5.4.3-1 имеем а « 0.897, j3 ~ 0.800 - 2. Время перемотки по этой таблице можно оценить как удвоенную разность ["проходы с копированием" минус "проходы без копирования"] плюс 1/(2Р) в том случае, если перед окончательным слиянием необходима перемотка для получения возрастающего порядка.

Пример 9. Осциллирующая сортировка с обратным чтением. В этом случае выбор с замещением должен многократно начинаться и останавливаться; за один раз распределяется от Р - 1 до 2Р - 1 серии (в среднем Р); средняя длина серий, следовательно, оказывается приблизительно равной Р(2Р-4/3)/Р и можно оценить 5 - [iV/((2-4/(3P))P)] -Ь1. Некоторое время расходуется на переключение от слияния к распределению и обратно; оно приблизительно равно времени, затрачиваемому на чтение Р записей с вводной ленты, а именно - PCuiT, и это происходит примерно 5/Р раз. Время перемотки и время слияния можно оценить, как в примере 6.

Пример 10. Осциллирующая сортировка с прямым чтением. Данный метод нелегко проанализировать, поскольку окончательная фаза "чистки", выполняемая после исчерпания исходных данных, не так эффективна, как предыдущие. Пренебрегая этим трудным аспектом и просто считая, что есть один дополнительный проход, можно оценить время слияния, полагая а = 1/1пР, /3 = 0и7г = тг/Р. Распределение серий в этом случае несколько иное, так как не используется выбор с замещением; мы устанавливаем Р = М/С и 5 = \N/P]. Приложив некоторые усилия, можно совместить вычисление, чтение и запись во время распределения, введя дополнительный коэффициент накладных расходов, равный приблизительно {М + 2В)/М. Время переключения режимов, упомянутое в примере 9, в настоящем случае не нужно учитьшать, поскольку переключение совмещается с перемоткой. Итак, оценка времени сортировки имеет вид (9) плюс 2BNCuJiT/M.

Из табл. 1 следует, что полученные оценки достаточно хорошо совпадают с реальностью, хотя в нескольких случаях расхождение составляет порядка 50 с. Формулы в примерах 2 и 3 показывают, что каскадному слиянию нужно отдать

Таблица 1

СВОДНАЯ ТАБЛИЦА ОЦЕНОК ВРЕМЕНИ СОРТИРОВКИ

предпочтение перед многофазным на шести лентах, тем не менее на практике многофазное слияние лучше! Причина этого кроется в том, что графики, подобные изображенным на рис. 85 (на котором показан случай для пяти лент), ближе к прямым линиям для многофазного алгоритма; каскадный метод превосходит многофазный на шести лентах для 14 < 5 < 15 и 43 < 5 < 55 вблизи "точных" каскадных чисел 15 и 55, но многофазное распределение по алгоритму 5.4.2D лучше или, по крайней мере, не хуже для всех остальных 5 < 100. Каскадный метод предпочтительнее многофазного при 5 -> ос, но на практике S не может быть слишком большим. Заниженная оценка в примере 9 обусловлена аналогичными обстоятельствами; многофазная сортировка лучше осциллирующей, несмотря на то что, как следует из асимптотического выражения, для больших 5 осциллирующая сортировка будет наилучшей.

Несколько дополнительных замечаний. Сейчас самое время сделать несколько более или менее случайных замечаний относительно ленточного слияния.

• Приведенные формулы показывают, что сортировка является, в сущности, функцией от произведения 7V и С, а не 7V и С по отдельности. За исключением нескольких относительно незначительных соображений (например, что В выбирается кратным С) из наших формул следует, что сортировка миллиона записей по 10 символов займет примерно столько же времени, сколько сортировка 100000 записей по 100 символов. На самом деле здесь может появиться различие, которое невозможно обнаружить в наших формулах, так как во время выбора с замещением некоторое пространство используется для полей связи. В любом случае размер ключа едва ли окажет какое-либо влияние, если только ключи не будут столь длинными и сложными, что внутренние вычисления не смогут угнаться за работой НМЛ.

При длинных записях и коротких ключах соблазнительно выделить ключи, рассортировать их, а затем как-нибудь переставить записи целиком. Но эта идея, кажется, не работает: она может только отсрочить агонию, поскольку процедура окончательной перестановки требует почти столько же времени, сколько потребовала бы общепринятая сортировка методом слияния.

• Разрабатывая программу сортировки, которая должна использоваться многократно, разумно очень тщательно оценить время работы и сравнить теорию с действительными наблюдаемыми характеристиками выполнения. Так как теория

сортировки развита довольно хорошо, эта процедура, как известно, способна внезапно выявить дефекты в оборудовании или программном обеспечении ввода-вывода в существующих системах. Оказывается, обслуживание выполнялось медленнее, чем следовало, и никто этого не замечал, пока данный недостаток не проявился на программе сортировки!

• Наш анализ выбора с замещением был выполнен в предположении, что данные в файле расположены случайно, но файлы, встречающиеся на практике, очень часто уже являются упорядоченными в той или иной степени. (Фактически иногда пользователи обращаются к сортировке файлов, уже упорядоченных ранее, только для того, чтобы убедиться в этом.) Таким образом, опыт даже в большей мере, чем указывают наши формулы, показал, что выбор с замещением предпочтительнее других видов внутренней сортировки. Данное преимущество несколько ослабляется в случае многофазной сортировки с обратным чтением, так как должен быть порожден ряд убывающих серий; на самом деле Р. Л. Гилстад (R. L. Gilstad) (он первым опубликовал описание метода многофазного слияния) первоначально по этой причине отверг метод обратного чтения. Но позднее он заметил, что чередование направлений будет все же давать длинные возрастаюпще серии. Кроме того, многофазный метод с обратным чтением - это единственный стандартный метод, который благосклонен к убывающим входным файлам в той же степени, что и к возрастающим.

• Другое преимущество выбора с замещением состоит в том, что этот метод допускает совмещение процессов чтения, записи и вычислений. Если бы мы просто выполняли внутреннюю сортировку очевидным способом - заполнили память, расссортировали данные в ней и затем записывали данные по мере того, как память заполняется новым содержимым, - то проход распределения занял бы примерно вдвое больше времени.

Из рассмотренных нами методов внутренней сортировки еще только один можно приспособить к одновременному чтению, записи и вычислениям - пирамидальную сортировку. (Эта идея была использована при подготовке примера 10 диаграммы А.) Предположим для удобства, что внутренняя память содержит 1 ООО записей, а каждый блок на ленте - по 100. Действовать можно следующим образом (через В2 Вю обозначено содержимое памяти, разделенной на 10 блоков по 100 записей).

Шаг 0. Заполнить память и сделать так, чтобы элементы В2 Вю удовлетворяли неравенствам пирамиды (с наименьшим элементом в вершине).

Шаг 1. Свести Bi... Вю в пирамиду, затем выбрать наименьшие 100 записей и переписать их в Вю.

Шаг 2. Записать из Вю; в то же время выбрать наименьшие 100 записей из Bi ... Bg и поместить их в Bg.

Шаг 3. Прочитать в Вю и записать в Bg; в то же время выбрать наименьшие 100 записей из Bi... Bg и поместить их в Bg.

Шаг 9. Прочитать в В4 и записать из Вз; в то же время выбрать наименьшие 100 записей из Bi В2, поместить их в Вг и сделать так, чтобы неравенства пирамиды были справедливы для В5 ... Вю-