Суть метода состоит в том, что массив разбивается на части, которые сортируются по отдельности, и в последующем составляются из нескольких уже упорядоченных массивов искомого массива. После того как части упорядочены, можно объединить их в одни другой упорядоченный массив , который потом объединяют в другой упорядоченный массив, ну и наконец объединяют в один массив. Для решения задачи сортировки эти три этапа выглядят так:
Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; Два упорядоченных массива половинного размера соединяются в один. Слияние имеет большое практическое применение. Например у Вас есть 2 списка номеров телефонов , отсортированных по возрастанию и их нужно объединить в один список, тоже отсортированный по возрастанию. Перейдем к алгоритму- коду задачи на объединение двух упорядоченных массивов !
const n1 = 5; n2 = 8;
var P: array [1..n1 + n2] of integer; M: array [1..n1] of integer; N: array [1..n2] of integer; i, j,l, x: integer;
begin writeln('Заполните массив M (ввод ', n1, ' элементов )'); for i := 1 to n1 do read(M[i]); writeln('Заполните массив N (ввод ', n2, ' элементов )'); for i := 1 to n2 do read(N[i]); j := 1; l := 1; for i := 1 to n1+n2 do if j>n1 then begin P[i] := N[l]; l := l+1; end else if l>n2 then begin P[i] := M[j]; j := j+1; end else if M[j]<=N[l] then begin P[i] := M[j]; j := j+1; end else begin P[i] := N[l]; l := l+1; end; for i := 1 to n1 + n2 do write(P[i]:3); end.
Усложним задачку (пример использования кода).
ДЗ. Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем.
Ну, а здесь, код-сортировка простым слиянием
Procedure MergeSort(name: string; var f: text); Var a1,a2,s,i,j,kol,tmp: integer; f1,f2: text; b: boolean; Begin kol:=0; Assign(f,name); Reset(f); While not EOF(f) do begin read(f,a1); inc(kol); End; Close(f); Assign(f1,'{имя 1-го вспомогательного файла}'); Assign(f2,'{имя 2-го вспомогательного файла}'); s:=1; While (s<kol) do begin Reset(f); Rewrite(f1); Rewrite(f2); For i:=1 to kol div 2 do begin Read(f,a1); Write(f1,a1,' '); End; If (kol div 2) mod s<>0 then begin tmp:=kol div 2; While tmp mod s<>0 do begin Read(f,a1); Write(f1,a1,' '); inc(tmp); End; End; While not EOF(f) do begin Read(f,a2); Write(f2,a2,' '); End; Close(f); Close(f1); Close(f2); Rewrite(f); Reset(f1); Reset(f2); Read(f1,a1); Read(f2,a2); While (not EOF(f1)) and (not EOF(f2)) do begin i:=0; j:=0; b:=true; While (b) and (not EOF(f1)) and (not EOF(f2)) do begin If (a1<a2) then begin Write(f,a1,' '); Read(f1,a1); inc(i); End else begin Write(f,a2,' '); Read(f2,a2); inc(j); End; If (i=s) or (j=s) then b:=false; End; If not b then begin While (i<s) and (not EOF(f1)) do begin Write(f,a1,' '); Read(f1,a1); inc(i); End; While (j<s) and (not EOF(f2)) do begin Write(f,a2,' '); Read(f2,a2); inc(j); End; End; End; While not EOF(f1) do begin tmp:=a1; Read(f1,a1); If not EOF(f1) then Write(f,tmp,' ') else Write(f,tmp); End; While not EOF(f2) do begin tmp:=a2; Read(f2,a2); If not EOF(f2) then Write(f,tmp,' ') else Write(f,tmp); End; Close(f); Close(f1); Close(f2); s:=s*2; End; Erase(f1); Erase(f2); End;
| 
