// Sortowanie przez scalanie (mergesort)
// Tomasz Lubinski
// (c)2006 www.algorytm.org

program MergeSortProg;
{$APPTYPE CONSOLE}
uses
  SysUtils;

const N = 30;
var
  i: Integer;
  tab: array[0..N-1] of Integer = (30,29,28,27,26,25,1,2,3,4,5,6,7,24,23,22,21,20,19,18,8,9,10,11,17,16,15,13,14,12);
  t: array[0..N-1] of Integer; //Tablica pomocnicza

// Scalanie dwoch posortowanych ciagow
//   tab[pocz...sr] i tab[sr+1...kon] i
//   wynik zapisuje w tab[pocz...kon]
procedure merge(pocz: Integer; sr: Integer; kon: Integer);
var
  i,j,q : Integer;
begin

  for i:=pocz to kon do t[i]:=tab[i];     // Skopiowanie danych do tablicy pomocniczej
  i:=pocz; j:=sr+1; q:=pocz;              // Ustawienie wskaźników tablic
  while (i<=sr) and (j<=kon) do 	  // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
    begin
       if (t[i]<t[j]) then
          begin
             tab[q]:=t[i];
             i:=i+1;
          end
       else
          begin
             tab[q]:=t[j];
             j:=j+1;
          end;
       q:=q+1;
    end;
  while (i<=sr) do                        // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
     begin
        tab[q]:=t[i];
        q:=q+1;
        i:=i+1;
     end;
end;

// Procedura sortowania tab[pocz...kon]
procedure mergesort(pocz: Integer; kon: Integer);
var
  sr: Integer;
begin
  if (pocz<kon) then
    begin
       sr:=(pocz+kon) div 2;
       mergesort(pocz, sr);    // Dzielenie lewej części
       mergesort(sr+1, kon);   // Dzielenie prawej części
       merge(pocz, sr, kon);   // Łączenie części lewej i prawej
    end;
end;

begin

writeln('Zbior przed sortowaniem:');
for i:=0 to N-1 do
   write(IntToStr(tab[i]) + ' ');

mergesort(0,N-1);

writeln('');
writeln('Zbior po sortowaniu:');
for i:=0 to N-1 do
   write(IntToStr(tab[i]) + ' ');

readln;
end.