program tri;

{uses crt;}

const long_tab = 8;
type table = array[1..long_tab] of integer;

procedure saisie(var t:table);
var i,res : integer;
begin	  
   for i:=1 to long_tab do
   begin
      write(i,' ieme element ? : ');
      readln(res);
      t[i]:=res;
   end;
end; { saisie }


procedure visu(t:table);
var i : integer;
begin 
   write('[');
   for i:=1 to long_tab-1 do
   begin
      write(t[i],' ; ')
   end;
   writeln(t[long_tab],']')
end; { visu }


procedure swap(i,j : integer ; var t : table);
var aux	: integer;
begin
   aux:=t[i];
   t[i]:=t[j];
   t[j]:=aux;
end; { swap }



procedure tri_bulle(var t : table);
var j,k : integer;
begin
   for j:=long_tab downto 2 do
      for k:=1 to j-1 do
	 if t[k]>t[k+1] then swap(k,k+1,t);
end; { tri_bulle }


procedure tri_insertion(var t : table);
var j,k	: integer;
begin
   for k:=2 to long_tab do
      begin
	 j:=k;
	 while ((t[j-1]>t[j]) AND (j>1)) do
	 begin
	    swap(j,j-1,t);
	    j:=j-1;
	 end
      end
end; { tri_insertion }



procedure tri_selection(var t : table);
var max_tmp,indice_max,k,i: integer;
begin
   for k:=long_tab downto 2 do
   begin
      max_tmp:=t[1];
      indice_max:=1;
      for i:=2 to k do
      begin
	 if t[i]>max_tmp then
	    begin
	       max_tmp:=t[i];
	       indice_max:=i;
	    end
      end;
      swap(indice_max,k,t);
   end
end; { tri_selection }

procedure tri_neuneu(deb,fin :integer; var t : table);
var t1,t2 : integer;
begin
   if fin=deb+1 then
   begin
      if t[deb]>t[fin] then swap(deb,fin,t)
   end
   else if fin>deb+1 then
   begin
      t1:=deb+((1+fin-deb) div 3);
      t2:=deb+((2*(1+fin-deb)) div 3)-1;
      tri_neuneu(deb,t2,t);
      tri_neuneu(t1,fin,t);
      tri_neuneu(deb,t2,t);
      end
end; { tri_neuneu }


procedure tri_fusion(deb,fin :integer; var t : table);
var milieu,c1,c2,c3,i : integer;
   t_intermediaire : table;
begin
   if deb<>fin then
      begin
	 milieu:=(deb+fin) div 2;
	 tri_fusion(deb,milieu,t);
	 tri_fusion(milieu+1,fin,t);
	 c1:=deb; c2:=milieu+1; c3:=deb;
	 while ((c1<=milieu) or (c2<=fin)) do
	 begin
	    if (c1>milieu) or ((c2<=fin) and (t[c2]<t[c1]))
	       then
	    begin {on avance le compteur de droite}
	       t_intermediaire[c3]:=t[c2];
	       inc(c2)
	    end
	    else
	    begin {on avance le compteur de gauche}
	       t_intermediaire[c3]:=t[c1];
	       inc(c1)
	    end;
	    inc(c3)
	 end;
	 for i:=deb to fin do t[i]:=t_intermediaire[i];
      end;
end; { tri_fusion }


var T:table;

begin
   T[1]:=-1515;
   T[2]:=-15;
   T[3]:=5;
   T[4]:=-2235;
   T[5]:=115;
   T[6]:=0;
   T[7]:=1515;
   T[8]:=1;
   visu(T);
   readln;
   tri_neuneu(1,long_tab,T);
   readln;
   visu(T);
   readln;
end.