Алгоритм сортировки слиянием

Пусть сортируемая последовательность F = { f1, …, fN } представлена в виде двух уже отсортированных половин — F1 и F2. Тогда для сортировки F достаточно слить (т.е. применить аналог алгоритма слияния FileMerge) последовательности F1 и F2 в выходную последовательность G. Поскольку упорядоченные половинки F1 и F2 можно получить с помощью тех же действий, мы можем описать алгоритм сортировки слияниями рекурсивно. При этом, очевидно, необходимо использовать оптимальное количество промежуточных файлов. Поскольку слияния нужно начинать с однокомпонентных файлов, точная реализация описанного алгоритма потребует 2N дополнительных файлов, что, конечно, неприемлимо. Поэтому мы должны использовать один файл для хранения нескольких сливаемых подпоследовательностей. Уточним эту идею:

Пусть сортируемый файл F содержит k-элементные упорядоченные подпоследовательности A1, A2, …, A2l, k = 2l.

1. Разделение F заключается в переписи подпоследовательностей Aj с четными номерами в файл F1, а с нечетными номерами — в файл F2.

Пусть файл F1 содержит k-элементные упорядоченные подпоследовательности B1, B3, …, B2l-1, а F2 — k-элементные упорядоченные подпоследовательности B2, B4, …, B2l.

2. Слияние F1 и F2 заключается в слияниях пар в подпоследовательности A (i+1) div 2 в файл F. После обработки F будет содержать l 2k-элементных подпоследовательностей Aj.

Если N — степень 2-x (N = 2m), то после m-кратного повторения разделения-слияния, начиная с A1={f1}, …, AN={fN}, файл F будет содержать отсортированную последовательность. В общем случае, когда N 2m, управление слияниями-разделениями немного усложняется:

• — при разделении количество подпоследовательностей может оказаться нечетным;
• — при слиянии последняя по счету подпоследовательность одного из файлов может иметь меньшее, чем все другие, количество элементов.

Program MergeSort;

Type Component = Record.

Key: Integer; { поле ключа }.

Data: String[20] { поле данных}.

End;

OurFile = File of Component;

Var F, F1, F2: OurFile;

k, L, t, SizeF: Integer;

{Procedure FileOut (var F: OurFile);}.

{Procedure FileInp (var F: Ourfile);}.

Procedure CopyBlock (Var U, V: OurFile; k: Integer);

Var i: Integer;

X: Component;

Begin.

For i := 1 to k do begin.

Read (U, X); Write (V, X).

end.

End;

{ разделение блоками по k компонент F ==> F1, F2 }.

Procedure Partition (k: Integer);

Var i: Integer;

Begin.

Reset (F); Rewrite (F1); Rewrite (F2);

For i:= 1 to L do.

If Odd (i).

then CopyBlock (F, F1, k).

else CopyBlock (F, F2, k);

If Odd (L).

then CopyBlock (F, F2, t).

else CopyBlock (F, F1, t);

Close (F1); Close (F2).

End;

{ слияние блоками по k компонент F1, F2 ==> F }.

Procedure Merge (k: Integer);

Var i: Integer;

Procedure MergeBlock (t: Integer);

Var count1, count2: Integer;

X1, X2: Component;

Flag: Boolean;

Procedure AppendTail (var U: Ourfile; var p: Integer; s: Integer);

Var A: Component;

Begin.

While p <= s do begin.

Read (U, A); Write (F, A); p := p + 1.

end;

End { AppendTail };

Procedure Step (var U: OurFile; Var A, B: Component; var p, q: Integer; s: Integer);

begin.

Write (F, A); p := p + 1;

If p <= s.

then Read (U, A).

else begin Write (F, B); q := q + 1; Flag := False end.

end { Step };

Begin { MergeBlock }.

count1 := 1; count2 := 1; Flag := True;

Read (F1, X1); Read (F2, X2);

While Flag do.

If X1. Key < X2.Key.

then Step (F1, X1, X2, count1, count2, k).

else Step (F2, X2, X1, count2, count1, t);

AppendTail (F1, count1, k); AppendTail (F2, count2, t);

end { MergeBlock };

Begin { Merge }.

Rewrite (F); Reset (F1); Reset (F2);

For i := 1 to (L div 2) do MergeBlock (k);

If t 0.

then if Odd (L).

then MergeBlock (t).

else CopyBlock (F1, F, t).

else if Odd (L).

then CopyBlock (F1, F, k).

End { Merge };

Procedure FirstPartition;

Var X: Component;

Begin.

Reset (F); Rewrite (F1); Rewrite (F2);

SizeF := 0;

While not (Eof (F)) do begin.

Read (F, X); SizeF := Succ (SizeF);

If Odd (SizeF).

then Write (F1, X).

else Write (F2, X).

end;

Close (F1); Close (F2).

End { FirstPartition };

Begin {Определение внешних имен файлов F, F1, F2}.

FileInp (F);

FirstPartition; {первое разделение с подсчетом SizeF}.

L := SizeF; t := 0;

Merge (1); {первое слияние 1-блоков}.

k := 2;

While k < SizeF do begin.

L := SizeF div k; {количество полных k-блоков в F}.

t := SizeF mod k; { размер неполного k-блока }.

Partition (k);

Merge (k);

k := 2*k.

end;

FileOut (F);

End.

Оценим сложность алгоритма в терминах С (n), M (n), L (n), где L (n) — число прогонов файла F и n = SizeF.

1. Оценка L (n).

L (n)= число разделений + число слияний. Каждое разделение — вызов процедуры Partition, а слияние — вызов Merge. Поэтому L (n) — удвоенное число повторений тела цикла While. Отсюда, поскольку переменная k, управляющая циклом, каждый раз увеличивается вдвое, на L-том шаге k = 2L, и, следовательно, L — наибольшее число такое, что 2L < n, т. е. L = [log2 n].

L (n) = 2[log2n].

2. Оценка С (n).

Сравнения копонент по ключу производятся при слиянии. После каждого сравнения выполняется процедура Step, которая записывает одну компоненту в F. Поэтому при каждом слиянии количество сравнений не превосходит n. Отсюда C (n) L (n)*n/2, т. е.

С (n) n [log2 n].

3. Оценка M (n).

Процедуры Partition и Merge пересылают компоненты файлов. Независимо от значений ключей вызов каждой из них либо читает F, либо записывает F. Поэтому M (n) = nL (n), т. е.

M (n) = 2n[log2 n].

Полученные оценки позволяют классифицировать алгоритм как эффективный алгоритм сортировки последовательных файлов. Его также можно адаптировать к сортировке массивов.

Алгоритм сортировки слиянием может быть улучшен несколькими способами. Рассмотрим только некоторые из них:

а. Заметим, что процедура Partition носит вспомагательный характер. Не анализируя ключей, она просто формирует файлы F1 и F2 для слияния. Поэтому ее можно исключить, если процедуру Merge заставить формировать не F, а сразу F1 и F2. При этом, конечно, количество файлов в программе увеличится. Именно:

• 1. F разделим на (F1, F2).
• 2. Определим вспомогательные файлы G1, G2
• 3. Основной цикл алгоритма:

Слияние (F1, F2) ===> (G1, G2);

Слияние (G1, G2) ===> (F1, F2);

(Нечетные пары блоков сливаем на 1-ый файл, четные — на 2-ой).

Временная сложность алгоритма улучшается почти вдвое.

б. Заметим, что на начальной стадии работы алгоритма размеры блоков малы. Их можно сортировать в оперативной памяти, используя представление в виде массива и быстрые алгоритмы сортироки массивов. Таким образом, следует изменить процедуру FirstPartition, определив ее как процедуру внутренней сортировки k0-блоков при некотором (максимально возможном) значении k0. Цикл While основной программы теперь можно начинать с k = k0.

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