в указанной работе Мак-Аллестер предложил взять

Un = Vn~l+ Vn-2 + Vn-3 + Vn-i, Vn+1 = Un-l + Un-2 + Wn-3 + U„ 4,

так что последовательность

{XQ,Xi,X2,Xz,XA,Xb,. . .) = {Vo, Uq, fi, Ui, f2, 2, . . .)

удовлетворяет однородному рекуррентному соотношению х„ = Хп-з+Хп-ь+Хп-т + Хп-9- Оказалось, однако, что лучше положить

Vn+l = U„ l + Vn-1 + Un-2 + Vn-2, Un - Un~3 + Vn-3 + Un-4 + fn-4-

(23)

Эта последовательность не только немного лучше по времени слияния; ее большое преимущество состоит в том, что соответствующее время слияния можно проанализировать математически. Вариант Мак-Аллестера для анализа крайне труден, потому что в одной фазе могут встречаться серии разной длины; мы увидим, что такого не может случиться, если справедливо (23).

Можно вывести число серий на каждой ленте на каждом уровне, двигаясь назад по схеме (21), и получить следующую схему сортировки.

Несовмещенная перемотка встречается только при перемотке вводной ленты Т5 (82 единицы) в течение первой половины фазы второго уровня (27 единиц) и в течение окончательных фаз "фиктивного слияния" на уровнях 1 и О (36 единиц). Таким образом, время работы можно оценить величиной 273f -- 145г; для алгоритма D соответствующий параметр 268f -I- 208г почти всегда хуже.

Нетрудно видеть (см. упр. 23), что длины серий, выводимых во время каждой фазы, суть

4,4,7,13,19,31,52,82,133,..., (24)

при этом последовательность {*i, *2, з» • • •) удовлетворяет закону

tn = tn-2 + 2*„ з + tn-4,

если считать tn = I при п < 0. Можно также проанализировать оптимальное размещение фиктивных серий, рассмотрев цепочки чисел слияний, как для стандартного многофазного метода [ср. с (8)].

(26)

Здесь An = АпАп п А! состоит из последних и„ чисел слияний Л„. Приведенное выше правило перехода с уровня п на уровень п -Ь 1 справедливо для любой схемы, удовлетворяющей (22). Если определить и„ и f„, как в (23), то цепочки Л„,...,Еп можно выразить в следующем, довольно простом, виде [ср. с (9)]:

An = {Wn-lWn-2Wn-3Wn-4) + 1, B„ = {Wn-lWn-2Wn-3) + l, Cn = {Wn-lWn-2) + 1, Dn = (Wn-l) + l, En = {Wn-2Wn-3) + 1,

при n > О,

(27) (28)

Wn = (Wn-3Wn-4Wn-2Wn-3) + 1

Wo = 0 и Wn = c при n < 0.

Исходя из этих соотношений, легко подробно проанализировать случай для шести лент.

В общем случае, если имеется Т > 5 лент, положим Р = Т - 2 и определим последовательности (и„), (f„) по правилам

(29)

Vn+l = Un-1 -\- Vn-l + + Un-r + Vn-r,

Un = Un-r-1 + Vn-r-l + • • • -b Un-P + Vn-P при П > 0,

где г = [P/2J, Do = 1 и u„ = D„ = о при n < 0. Если ш„ = u„ -Ь f„, то имеем

Wn = Wn-2 Н-----Ь Wn-r + 2u;„ r-i + Wn-r-2 Н-----Ь Wn-p при n > 0; (30)

Wo = 1 и u;„ = О при n < 0. При начальном распределении для уровня п -I-1 на ленту

к помещается и;„ + Wn-i л-----Ь Wn-p+k серий при 1 < А; < Р и Wn-i Н-----h Wn-r -

на ленту Т; лента Т - 1 используется для ввода. Затем и„ серий сливаются на ленту Г, в то время как лента Г - 1 перематывается; серий сливаются на Г - 1, пока Т перематывается; u„ i серий сливаются на Т - 1, пока Т - 2 перематывается, и т. д.

Таблица 6

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

В табл. 6 показаны приблизительные данные о ходе выполнения этой процедуры, когда S не слишком мало. В столбце "Проходы/фазы" примерно показано, какая часть всего файла перематывается во время каждой половины фазы и какая часть файла записывается за время каждой полной фазы. Метод расщепления лент превосходит стандартный многофазный метод на шести или более лентах и, вероятно, также на пяти лентах, по крайней мере для больших S.

Если Г = 4, то указанная процедура стала бы, по существу, эквивалентной сбалансированному двухпутевому слиянию без совмещения времени перемотки, так как W2nJfi было бы равно О при всех п. Поэтому элементы табл. 6 при Т = 4 были получены посредством небольшой модификации, состоящей в том, что полагалось V2 = о, ui = 1, vi = о, uo = О, Vo = 1 иг;„+1 = u„ i+r;„ i, u„ = и„ 2+г;„ 2 прип > 2. Это позволяет построить очень интересную схему сортировки (см. упр. 25 и 26).

УПРАЖНЕНИЯ

1. [16] На рис. 69 указан порядок, в котором алгоритм D распределяет по пяти лентам серии 34-65. В каком порядке распределяются серии 1-33?

► 2. [21] Верно ли, что после двух фаз слияния в алгоритме D, т. е. когда мы во второй раз достигаем шага D6, все фиктивные серии исчезают?

► 3. [22] Докажите, что по окончании шага D4 всегда выполняется условие D[l] > D[2] > • • • > D [Г]. Объясните важность этого условия для правильной работы на шагах D2 и D3.

4. [М20] Выведите производящие функции (7).

5. [НМ26] (Э. П. Майлс (Е. Р. Miles, Jr.), 1960.) Докажите, что при всех р>2 многочлен fp{z) = z*" -z*"" - -z - l имеетp ргизличных корней, из которых ровно один превосходит 1 по абсолютной величине. [Указание. Рассмотрите многочлен z+ - 2z + 1.]

6. [НМ24] Цель этого упражнения - рассмотреть способ составления табл. 1, 5 и 6. Предположим, что имеется схема слияния, свойства которой следующим образом характеризуются многочленами p{z) и q{z). (i) Число начальных серий в "точном распределении", требующем п фаз слияния, равно [z"]p{z)/q{z). (ii) Число начальных серий, обрабатываемых в течение этих п фаз слияния, равно [z]p{z)/q{z). (iii) У многочлена q{z~) есть "главный корень" а, такой, что q{a-) = О, q{a~) ф О, р(а~) О, и из д(/3~) = О следует, что /3 = Q или < а.

Докажите, что существует б > О, такое, что если S равно числу серий при точном распределении, требующем п фаз слияния, а во время выполнения этих фаз обрабатывается