Таблица 2

число СЕРИЙ, ПРИ КОТОРОМ ДАННЫЙ УРОВЕНЬ ОПТИМАЛЕН

4- или 5-го уровня, общее количество операций в процессе слияния будет только е4(17) = s5(17) = 35. Выгоднее применять 4-й уровень, хотя число 17 соответствует "точному" распределению 3-го уровня! В самом деле, по мере возрастании S оптимальный номер уровня оказывается значительно больше номера, используемого в алгоритме D.

В упр. 14 показано, что существует неубывающая последовательность М„, такая, что уровень п оптимален для М„ < S < M„+i, но не для 5 > M„+i. В случае для шести лент только что вычисленная таблица Е„(т) дает

Мо = 0, Ml = 2, М2 =6, Мз = 10, м4 = 14.

Выше рассматривался только случай для шести лент, однако ясно, что те же идеи применимы к многофазной сортировке с Т лентами для любого Т > 3; просто в соответствующих местах необходимо заменить 5 на Р = Т - 1. В табл. 2 представлены последовательности М„, полученные для различных значений Т. Табл. 3 и рис. 72 дают представление об общем количестве обрабатываемых начальных серий после оптимального распределения фиктивных серий. (Формулы внизу табл. 3 следует принимать с осторожностью, так как это приближение по методу наименьших квадратов на области 1 < 5 < 5000 (1 < 5 < 10000 для Т = 3), что приводит к отклонению (данная область значений S не является одинаково подходящей для всех Т). По мере того, как 5 оо, число обрабатываемых начальных серий после оптимального многофазного распределения асимптотически приближается к 51ogp S, но это приближение происходит крайне медленно.)

При помощи табл. 4 можно сравнить метод распределения алгоритма D с результатами оптимального распределения, приведенными в табл. 3. Ясно, что алгоритм D

T = 3

7 = 4

T = 5

T = (, T = l T = 9 T=10

10 20 50 100 200

Начальные серии, S

500 1000 2000

5000

Рис. 72. Эффективность многофазного слияния с оптимальным начальным распределением при тех же предположениях, что и на рис. 70.

Таблица 3

число НАЧАЛЬНЫХ СЕРИЙ, ОБРАБАТЫВАЕМЫХ ПРИ ОПТИМАЛЬНОМ МНОГОФАЗНОМ СЛИЯНИИ

не очень близок к оптимальному при больших 5 и Г; однако непонятно, можно ли поступить в этих случаях существенно лучше алгоритма D, не прибегая к значительным усложнениям, особенно если S заранее неизвестно. К счастью, заботиться о больших 5 приходится довольно редко (см. раздел 5.4.6), так что алгоритм D на практике не так уж плох (а на самом деле - даже весьма неплох!).

Таблица 4

число НАЧАЛЬНЫХ СЕРИЙ, ОБРАБАТЫВАЕМЫХ ПРИ СТАНДАРТНОМ МНОГОФАЗНОМ СЛИЯНИИ

Математически многофазная сортировка впервые проанализирована У. К. Картером (W. С. Carter) [Ргос. IFIP Congress (1962), 62-66]. Многие из приведенных им результатов относительно оптимального размещения принадлежат Б. Сэкману (В. Sackman) и Т. Зингеру (Т. Singer) ["А vector model for merge sort analysis", неопубликованный доклад, представленный на симпозиуме ACM Sort Symposium (November, 1962), 21 pages]. Позднее Сэкман предложил метод распределения по горизонтали, используемый в алгоритме D. Дональд Шелл (Donald Shell) [САСМ 14 (1971), 713-719; 15 (1972), 28], независимо развив эту теорию, указал на соот-нощение (10) и подробно изучил несколько различных алгоритмов распределения. Дальнейшие полезные усовершенствования и упрощения были получены Дереком Э. Зэйвом (Derek А. Zave) [SICOMP 6 (1977), 1-39]; некоторые из результатов Зэйва рассматриваются в упр. 15-17. Производящая функция (16) впервые была исследована У. Буржем (W. Burge) [Ргос. IFIP Congress (1971), 1, 454-459].

А как обстоит дело с временем перемотки? До сих пор мы использовали число начальных обрабатываемых серий как единственную меру эффективности для сравнения стратегий слияния на лентах. Но после каждой из фаз 2-6 в примерах в начале этого раздела компьютер должен ожидать перемотки двух лент; обе выводные ленты - как предыдущая, так и новая текущая - должны быть перемотаны в начало, прежде чем сможет выполняться следующая фаза. Это может вызвать существенную задержку, так как в общем случае на предыдущей выводной ленте содержится значительный процент сортируемых записей (см. столбец "Проходы/фазы" в табл. 1). Досадно, когда компьютер простаивает при перемотке, тогда как в это время можно было бы, используя иную схему слияния, выполнять полезную работу с остальными лентами.

Данную задачу можно решить с помощью простой модификации многофазной процедуры, хотя она требует не менее пяти лент [см. диссертацию И. Сезари (Y. Cesari) (U. of Paris (1968), 25-27), в которой эта идея приписывается Ж. Карону (J. Сагоп)]. Каждая фаза схемы Карона сливает серии с Г-3 лент на любую другую ленту, в то время как оставшиеся две ленты перематываются.

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