program Mergesort_rekurzivni;

 {Tridici algoritmus Mergesort - rekurzivni verze}

 uses Crt; {Unita pro praci s obrazovkou}

 const MaxN = 100;

      {maximalni pocet tridenych cisel (dle potreby)}

 type  Pole = array[1..MaxN] of integer;      {tridena cisla}

 var P: Pole;     {ulozeni tridenych udaju}

     Q: Pole;     {Q je pomocne odkladaci pole pro realizaci slevani}

     N: 1..MaxN;  {pocet prvku v poli P}

     I: integer;

procedure Mergesort (var P,Q:Pole; Zac,Kon:integer);{Zacatek deklarace procedury }

{setridi v poli P usek od indexu Zac do indexu Kon}

{Q je pomocne odkladaci pole pro realizaci slevani}

var Stred:integer;    {index prostredku trideneho useku}

    i,j,k: integer;   {pomocné indexy pro slevani}

    begin    Stred:=(Zac+Kon) div 2;

       {konec leveho useku pri rozdeleni useku <Zac,Kon>}

    if Zac < Stred then Mergesort(P,Q,Zac,Stred);      {utridit levy usek}

    if Stred+1 < Kon then Mergesort(P,Q,Stred+1,Kon);  {utridit pravy usek}

{slevani  obou useku:}

 i:=Zac;{levy usek}   j:=Stred+1;{pravy usek}  k:=Zac;{vysledek}

 while (i<=Stred) and (j<=Kon) do    {slevani setridenych useku do pomocneho pole Q}

       begin if P[i]<=P[j] then

                        begin Q[k]:=P[i]; i:=i+1 end

                           else

                        begin Q[k]:=P[j]; j:=j+1 end;

             k:=k+1

       end;

 while i<=Stred do   {dokopirovani zbytku leveho useku}

            begin Q[k]:=P[i]; i:=i+1; k:=k+1 end;

 while j<=Kon do     {dokopirovani zbytku praveho useku}

            begin   Q[k]:=P[j]; j:=j+1; k:=k+1 end;

 {zbyva prenest setrideny usek <Zac,Kon> zpet z Q do P:}

 for k:=Zac to Kon do  P[k]:=Q[k]

 end;  {konec deklarace procedury Mergesort}



 begin  {hlavni program}

  clrscr; {Vymazani obrazovky}

  write('Pocet tridenych cisel: ');

  readln(N);  writeln;

  writeln('Zadani posloupnosti tridenych cisel:');

  for I:=1 to N do read(P[I]);

  Mergesort(P,Q,1,N);

  writeln;

  writeln('Setridena cisla:');   writeln;

  for I:=1 to N do write(P[I]:5);

  repeat until keypressed;

end.