procedure Copy

begin

y.Elem: =self.Elem;

write(y.f, y.Elem);

f.eof: =sustem.eof(f);

if not f.eof then read(f, f.elem);

f.eor: =f.eof or (f.elem< y.elem);

end;

Многофазная сортировка.

сначала происходит начальное распределение данных, а затем используется (N— 1)-путевое слияние, то есть все время серии берутся из N — 1 файлов и сливаются в один пустой. Чтобы (N — 1)-путевое слияние стало возможным, необходимо вначале распределить данные особым образом: распределение происходит на N — 1 вспомогательный файл, при этом количество серий в каждом из файлов зависит от количества вспомогательных файлов и количества серий в исходном файле. Поскольку последний параметр заранее не известен, то распределение серий происходит по уровням. Если в исходном файле одна серия, то на нулевом уровне все данные должны быть записаны в один файл. На всех остальных уровнях количество серий, которое должно быть распределено на каждый из вспомогательных файлов, определяется формулами:

где L — номер уровня, а N — количество вспомогательных файлов.

Нетрудно заметить, что количество серий в исходном файле может отличаться от такого идеального распределения. В этом случае считается, что в распоряжении имеются фиктивные (пустые) серии, причем их столько, что сумма пустых и реальных серий равна идеальной сумме. Заметим, что слияние пустых серий из всех N — 1источников означает, что никакого реального слияния не происходит, вместо него в выходную последовательность записывается результирующая пустая серия. Отсюда можно заключить, что пустые серии нужно как можно более равномерно распределять по N — 1последовательностям. Алгоритм " горизонтального распределения пустых серий", позволяет эффективно распределить серии.

1. Подсчитать число серий, которое должно быть распределено в каждый из вспомогательных файлов на данном уровне (a_i^L i = 1,..., N — 1).

2.Подсчитать количество серий, которое надо дописать в каждый из вспомогательных файлов на данном уровне, чтобы получить число серий, равное a_i^L: d_i^L = a_i^L - a_i^{L- 1}. После того как это число определено, считаем, что в каждый из вспомогательных файлов записано d_i^L пустых серий.

3. Пока не кончился исходный файл и пока не исчерпаны все пустые серии на данном уровне, заменяем пустую серию на реальную; при этом записываем ее в тот файл, в котором количество пустых серий максимально.

4. Если исходный файл не кончился, осуществляется переход на следующий уровень: L = L + 1 и переход к пункту 1.

Когда все данные распределены, происходит слияние данных: сначала сливаются данные из вспомогательных файлов с номерами 1, 2,..., N — 1 в N- ыйвспомогательный файл, при этом файл с номером N— 1 станет пустым (слияние на L- омуровне). Далее номер уровня уменьшается и происходит слияние файлов с номерами 1, 2,..., N — 1 в (N — 1)-ый файл, т. е. слияние на L — 1 уровне. Так продолжается до тех пор, пока номер уровня не станет равным 0. Заметим, что во время слияния на очередном уровне, если не кончились пустые серии, то в первую очередь объединяются они, поскольку их объединение требует меньше затрат.

Procedure Select (номер файла, куда пойдет запись реальной серии)

Var I, z: integer;

Begin

If d[j]< d[j+1] then inc(j)

Else begin

If d[j]= 0 then begin \\ нет фиктивн серий

Level: =level+1;

Z: =a[1];

For i: =1 to N-1 do begin

D[i]: =z+a[i+1]-a[i];

A[i]: =z+a[i+1]; end; end;

J: =1; end;

D[j]: =d[j]-1; end;

BEGIN

F0: =TSequance.Create (‘1.tmmp’);

For i: = 1 to N do

F[j]: =TSequance.Create (IntToStr(i)+’.tmp’)

Level: =1;

For i: =1 to n-1 do begin

A[i]: =1; d[i]: =1;

F[i].startWrite; end;

A[n]: =0; d[n]: =0;

F0.startRead; j: =1; \\ куда пишем серию

Repeat

Select; f0.CopyRun(f[j]);

Until f0.eof or (j=n-1);

While not f0.eof do begin

Select;

If f[j].elem< =f0.elem then begin

F0.copyrun(f[j]);

If f0.eof then inc(d[j]);

Else f0.copyrun(f[j]); end;

Else f0.copyrun(f[j]); end;

For i: =1 to n-1 do begin

F[i].StartRead; t[i]: =I; end;

T[n]: =n;

Repeat

Z: =a[n-1];

D[n]: =0;

F[t[n]].startwrite;

Repeat

K: =0;

For i: =1 to n-1 do

If d[i]> 0 then dec(d[i])

Else begin

Inc(k); ta[k]: =i; end;

If k=0 then \\ во всех есть фиктив серии

Inc(d[n]);

Else repeat

i: =1; mx: =1; \\ мин в карте индексов

min: =f[ta[1]];

while (i< k) do begin

inc(i); x: =f[ta[i]].elem;

if x< min then begin

min: =x; mx: =I; end; end;

f[ta[mx]].copy(f[t[n]]);

if f[ta[mx]].eor then begin

ta[mx]: =ta[k]; dec(k); end;

until k=0;

dec(z);

until z=0;

f[t[n]].startread;

tn: =t[n]; dn: =d[n]; i: =a[n-1];

for i: = n downto 2 do begin

t[i]: =t[i-1]; d[i]: =d[i-1];

a[i]: =a[i-1]-z; end;

t[1]: =tn; d[1]: =dn; a[1]: =z;

f[t[n]].startwrite;

level: =level-1;

until level=0;

f[t[1]].copyAll(f0);

for i: =1 to N do begin

f[i].clear; f[i].Erase;

f[i].destroy; end;

fo.destroy;

END

Каскадная сортировка

похожа на многофазную сортировку. Отличие заключается в самом процессе слияния: сначала проводится (N — 1 ) — путевое слияние в N -ый файл до тех пор, пока файл с номером N— 1 не опустеет; затем (N -ый файл уже не затрагивается) проводится (N — 2) — путевое слияние в (N— 1)-ый файл; затем (N— 3) — путевое в (N— 2)-ый файл;...; потом двухпутевое слияние в третий файл, а в конце копирование из файла с номером 2 в первый файл. Следующий проход работает по аналогичной схеме, только в обратном направлении. Поскольку слияние в каскадной сортировке отличается от слияния в многофазной сортировке, то и начальное распределение данных осуществляется по-другому — количество серий в каждом из вспомогательных файлов должно быть другим. Оно определяется в соответствии с формулами:

или

Н. Вирт пишет: " Хотя такая схема выглядит хуже многофазного слияния, поскольку некоторые последовательности " простаивают", и есть просто операции копирования, тем не менее, она, что удивительно, оказывается лучше многофазной сортировки при очень больших файлах и шести или более последовательностях". Заметим, что при хорошей реализации алгоритма каскадной сортировки, от копирования можно избавиться, используя карты индексов.