последнего элемента последней серии каждой ленты. этого мы вводим переменную

last: array[/apmo] of integer

Теперь алгоритм распределения можно представить следующим образом:

repeat selecttape;

if lasAj] < /ОТ -key then

продолжение прежней серии ; (2.Щ

copyrun; lastlj} := /ОТ -key mm eofWO)

Здесь содержится очевидная ошибка: мы забыли о том что last[j] получает (определенное) значение только после переписи первой серии! Правильное решение состоит в том, что вначале распределяется по одной серии на каждую нз п-1 лент без обращения к last[j]. Оставшиеся серии рас- пределяются согласно (2.49):

while -neof(fO) do bein selecttape;

if Ш[Д < /ОТ .key then

l egin [продолжение прежней серии]

copyrun; (2.49)

if eofifO) then d[j1 := dlJ] + 1 else copyrun end

else copyrun

Предполагается, что присваивание значений last[j] включено в процедуру copyrun.

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

1. На каждом проходе имеется только одна выходная ленте, вместо п/2.

2. Вместо переключения п/2 входных и п/2 выходных леи' - после каждого прохода ленты чередуются. Этю достигаете* . с помощью карты ленточных индексов t.

ццсло ВХОДНЫХ лент меняется от серии к серии; в начале каждой серии оно определяется по счетчикам di фиктивных серий. Если di > О для всех i, то п - 1 фиктивных серий сливаются в одну фиктивную серию при помощи простого увеличения счетчика dn выходной ленты. В противном случае со всех лент, у которых di = О, сливается по одной серии, а для всех остальных лент di уменьщается, т означает исключение одной фиктивной серии. Число входных лент, участвующих в слиянии, мы обозначаем через к.

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

Теперь, согласно этим правилам, сформулируем основную часть алгоритма многофазной сортировки, предполагая, что все п-1 лент с начальными сериями перемотаны на начало и установлены начальные значения в карте ленточных индексов ti = i:

repeat [слияние с t[l] ... t[n - 1] на t[n]] z := a[n-l]; ф] := 0; rewnte(J\t[nJ[); repeat к := 0; [слияние одной серии]

[определение числа к входных лент, участвующих в слиянии^ for I := 1 to и-1 do if d[i\ > Q tlien d[i] := d[i] -1 else begin к :=k+l; ta[k] := t[q end ;

if = 0 then d[n] := d[n] + 1 else

слияние одной действительной серии с t[l] .. J[k]

z := z-1 until г = 0; reset(f[t[nS);

переключение лент в карте t; вычисление й[/] для следующего уровня ;

rewrite(J[t[nS); level := level - 1 til level = 0;

опгсортированный файл находится на ([Ц ]

(2.50)

Операция действительного слияния почти идентична программой п-путевой сортировки слиянием, единственная

program poly sort (output); {многофазная сортировка с n лентами} const к = 6; {числолент}

type item = record

кеу'. integer end ; tape == file otitem; tapeno - 1., и;

var leng, rand: integer; [используются оля формирования фай/w) eot: boolean;

buf: item;

/0; tape; if 0-входная лента со случайными числами]

/; array [1.. и] of tape; procedure/to (var/: tape; n: tapeno);

mtrmTeger; begin z := 0;

writeln (TAPE, n: 2);

while -neof(f) do

Hegin read(f, buf); write(ouiput, buf.key: 5); z z+l; if z = 25 then

begin TV 7e/n (oi/(pMf); z :- 0 end

end ;

if z 9b Othenw/Ve/nXowPOJ rcset(f) end { if}-;

fTocedate polyphasesort; var i,jx,tn: tapeno; k, level: integer; a, d: array [й/)еио] of integer;

[аЩ-идеальное число серий на ленте]]

{йЩ-число фиктивных серий на ленте j] dn,xin,z: integer; last: array [tapeno] of integer;

{/с5/[/]-ключ конечной серии на менте j] t,ta: array [tapeno] of tqpeno;

[карты номеров Лент]

procedure 5e/ec/rape;

var i: tapeno; z: integer; begin

if 4;1 < 4У+1] tben J :== j+1 else begin if d[j] = Otisen

begin := level + 1; z :==