Здесь все перемотки, по существу, совмещены, за исключением фазы 9 ("фиктивная фаза" которая подготавливает окончательное слияние) и перемотки после начальной фазы распределения (когда перематываются все ленты). Если t есть время, необходимое для слияния стольких записей, сколько содержится в одной начальной серии, а г - время перемотки на одну начальную серию, то этому процессу необходимо около 182* -- 40г плюс время начального распределения и завершающей перемотки. Соответствующие выражения для стандартного многофазного метода, использующего алгоритм D, есть 140* + 104г, что несколько хуже, если г = *, и несколько лучше, если г = \t.

Все сказанное о стандартном многофазном методе приложимо к многофазному методу Карона; например, последовательность а„ теперь удовлетворяет рекуррентному соотношению

а„ = а„ 2 + ап~з + ап-4 (20)

вместо (3). Читателю будет полезно проанализировать этот метод таким же образом, как мы анализировали стандартный многофазный, поскольку это улучшит понимание обоих методов (см., например, упр. 19 и 20).

В табл. 5 сведены данные о многофазном методе Карона, аналогичные данным об обычном многофазном методе, приведенным в табл. 1. Заметим, что на самом деле при восьми и более лентах метод Карона становится лучше многофазного как по числу обрабатываемых серий, так и по времени перемотки, несмотря на то что он выполняет (Г - 3)-путевое слияние вместо (Г - 1)-путевого!

Таблица 5

ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ КАРОНА

Эти данные будут казаться парадоксальными, пока мы не поймем, что высокий порядок слияния не обязательно означает эффективную сортировку. В качестве крайнего рассмотрим случай, когда 1 серия помещается на ленту Т1 и п серий - на Т2, ТЗ, Т4, Т5; если поочередно выполнять слияния на Т6 и Т1, пока Т2, ТЗ, Т4, Т5 не станут пустыми, то время обработки будет соответствовать {2п + Зп) длинам начальных серий, т. е., по существу, будет пропорционально 5, а не 5log5, хотя все время производится пятипутевое слияние.

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

и т. д. Здесь "Вывод к" означает запись в к-й выводной файл, а "Ввод к" - его чтение. Можно устранить время перемотки, если использовать три ленты, как было предложено в работе L. Weisner, САСМ 5 (1962), 102:

и т. д. Здесь "Вывод k.f означает запись j-й трети к-го выводного файла, а "Ввод k.j" - ее чтение. В конце концов, будет исключено все время перемотки, если перемотка выполняется, по крайней мере, вдвое быстрее чтения/записи. Подобная процедура, в которой вывод в каждой фазе разделяется между лентами, назьшается расщеплением лент.

в работе R. L. McAllester, САСМ 7 (1964), 158-159, показано, что расщепление лент приводит к эффективному методу совмещения времени перемотки в многофазном слиянии. Этот метод можно использовать с четырьмя или более лентами, и он осуществляет {Т - 2)-путевое слияние.

Предположим снова, что имеется шесть лент, и попытаемся построить схему слияния, которая работает следующим образом, расщепляя вывод на каждом уровне (буквы "1" "О" и "R" обозначают соответственно ввод, вывод и перемотку).

(21)

Чтобы по окончании работы получить одну серию на ленте Т4, а остальные ленты сделать пустыми, необходимо иметь

V0 = 1, "о + f 1 = О,

Щ +V2 = U0 + Vo,

U2 + V3 = Щ + Vl + Uo + Vo,

из + V4 = U2 + V2 + Ui + Vl + Uo + Vq,

U4 + Vb - из + V3 + U2 + V2 + щ + Vl + Uo + Vq,

Ub + V6 = U4 + V4 + из + V3 + U2 + V2 + Ui + Vl + Uo + Vo

и t. д. в общем случае требуется, чтобы

Un + Vn+l = Wn-l + Vn-l + Un-2 + Vn-2 + Un-3 + Vn-3 + Un-i + U„-4 (22)

при всех п > о, если считать Uj - Vj =Q при всех j < 0.

Эти уравнения не имеют единственного решения. В самом деле, если положить все и равными нулю, то получится обычное многофазное слияние, причем одна лента будет лишней! Но если выбрать и„ и Vn+i, то время перемотки будет удовлетворительно совмещено.