Sortowanie MergeSort, czyli sortowanie przez scalanie jest to sortowanie typu “dziel i zwyciężaj”. Gotowy, działający przykład takiego algorytmu, wraz z komentarzem możemy zobaczyć niżej.

Program Sort;

const

nmax = 100; {max rozmiar tablicy}

type

tablica = array[1..nmax] of integer;

var

n, i : integer;

tab : tablica;

procedure Dodaj (var t: tablica; var ind: integer; var nowy: integer); {Wpisywanie element i

zwiekszanie indeksu}

begin

nowy := t[ind];

ind := ind + 1

end;

procedure Polacz (n1, n2, n3 : integer; var tab: tablica);{Scalanie dwoch posortowanych

wycinkow tablicy}

var

pomoc: tablica;

i, i1, i2: integer; {i- indeks przebiegajacy elementy dwoch wycinkow,

i1-indeks przebiegajacy elementy pierwszego wycinka}

begin

i1 := n1; {nadanie wartosci poczatkowej}

i2 := n2 + 1; {nadanie wartosci poczatkowej}

for i:= n1 to n3 do {dla kazdego elementu dwoch wycinkow}

if i1 > n2 then {jesli pierwszy wycinek jest pusty}

{wpisanie do pomoc[i] elementu tab[i2] oraz zwiekszenie indeksu i2}

Dodaj(tab, i2, pomoc[i])

else if i2 > n3 then {jesli drugi wycinek jest pusty}

Dodaj(tab, i1, pomoc[i])

else if tab[i1] < tab [i2] then

Dodaj(tab, i1, pomoc[i])

else

Dodaj(tab, i2, pomoc[i]); {przepisywanie elementow z tablicy pomocniczej do

wejsciowej na miejsca pierwszego i drugiego wycinka}

for i:= n1 to n3 do

tab[i]:= pomoc[i]

end;

procedure Sortuj (n1,n2: integer; var tab: tablica); {rekurencyjne sortowanie przez laczenie}

var polowa: integer;

begin

polowa := (n1 + n2) div 2; {wyznaczanie srodkowego indeksu}

if n1 < polowa then {jesli lewy odcinek zwiera wiecej niz 2 elementy}

Sortuj(n1,polowa,tab); {Sortuj lewy wycinek}

if polowa + 1 < n2 then {jesli prawy odcinek zwiera wiecej niz 2 elementy}

Sortuj(polowa +1,n2,tab); {Sortuj prawy wycinek}

Polacz(n1,polowa,n2,tab) {Scal dwa posortowane wycinki}

end;

begin

writeln( ‘Podaj rozmiar tablicy’);

readln(n);

writeln(‘Podaj elementy tablicy’);

for i := 1 to n do

read(tab[i]);

Sortuj(1,n,tab);

writeln(‘tablica posortowana:’);

for i:= 1 to n do

write(tab[i]);

readln

end.