program Mergesort_rekurzivni;
{Tridici algoritmus Mergesort - rekurzivni verze}

const MaxN = 100;          {maximalni pocet tridenych cisel}

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

var P: Pole;     {ulozeni tridenych udaju}
    Q: Pole;     {pomocne pro slevani}
    N: 1..MaxN;  {pocet prvku v poli P}
    I: integer;

procedure Mergesort(var P,Q:Pole; Zac,Kon:integer);
{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;   {pomocne 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;  {procedure Mergesort}

begin  {hlavni program}
write('Pocet tridenych cisel: ');
readln(N);
writeln('Zadani posloupnosti tridenych cisel:');
for I:=1 to N do read(P[I]);
Mergesort(P,Q,1,N);
writeln('Setridena cisla:');
for I:=1 to N do write(P[I]:5);
writeln
end.