Листинг 1. Сортировка слиянием

procedure merge(k: integer; { длина входной серии } fl, f2, gl, g2: file of recordtype);

var outswitch: boolean; { равна true, если идет запись в gl и false, если в g2 }

winner: integer; { номер файла с меньшим ключом в текущей записи }

used: array[1..2] of integer; { used[j] сообщает, сколько записей прочитано к настоящему времени из текущей серии файла f_j }

fin: array[1..2] of boolean; { fin[j]=true, если уже закончена серия из файла f_j:

либо прочитано k записей, либо достигнут конец файла f_j}

current: array[1..2] of recordtype; { текущие записи из двух файлов }

procedure getrecord(i: integer); { Перемещение по файлу fi, не выходя за конец файла или

конец серии. Устанавливается fin[i]=true, если достигнут конец серии или файла }

begin

used[i]:= used[i] + 1;

if (used[i]= k ) or(i = 1) and eof(fl) or (i = 2) and eof(f2) then

fin[i]:= true

else if i = 1 then read(fl, current[1])

else read(f2, current[2])

end; { getrecord }

begin { merge }

outswitch:= true; {первая объединенная серия записывается в gl}

rewrite(gl); rewrite(g2);

reset(fl); reset(f2);

while not eof(fl) or not eof(f2) do begin { слияние двух файлов }
{ инициализация }

used[l]:= 0,- used[2]:= 0;

fin[l]:= false; fin[2]:= false;

getrecord(l); getrecord(2);

while not fin[l] or not fin[2] do begin { слияние серий }

{ вычисление переменной winner (победитель) }

if fin[l] then winner:= 2 {f2 "побеждает" по умолчанию: серия из fl исчерпалась}

else if fin[2] then winner:= 1 {fl "побеждает" по умолчанию}

else {не исчерпалась ни одна из серий}

if curren t [1].key<current[2].key then winner:= 1

else winner:= 2;

if outswitch then write(gl, current[winner])

else write(g2, current[winner]); getrecord(winner)

end;

{ закончено слияние двух серий, далее надо "переключить" выходной файл и повторить процедуру }

outswitch:= not outswitch;

end

end; { merge }

Обратите внимание, что процедура merge, показанная в листинге 1, вовсе не требует, чтобы отдельная серия полностью находилась в памяти: она считывает и за­писывает последовательно запись за записью. Именно нежелание хранить целые се­рии в основной памяти заставляет нас использовать два входных файла. В противном случае можно было бы читать по две серии из одного файла одновременно.

Таблица 11.1. Сортировка слиянием

д) серии длиной 16

3 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 69 77 85 90 93 96

е) серии длиной 32