Листинг 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 current[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. Сортировка слиянием

28 3	93 10	54 65	30 90	10 69	8
31 5	96 40	85 9	39 13	8 77	10
а) исходные файлы
28 31	93 96	54 85	30 39	8 10	8
3 6	10 40	9 65	13 90	69 77	22
б) серии длиной 2
3 5	28 31	9 54	65 85	8 10	69
10 40	93 96	13 30	39 90	8 10	22
в) серии длиной 4
3 5 10 28 31 40		93 96	8 8	10 10 22 69 77
9 13 30 39 54 65		85 90
г) серии длиной 8
359	10 13 28 30 31		39 40 54	65 85 90
8 8 10	10 22 69 77

д) серии длиной 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