{ M A G A S I N I   R E A L I S E E R I M I N E   M A S S I I V I N A }


   const MAXN=100;
   type liige = integer; indeks = 1..MAXN;
        jada = array [indeks] of liige;
        indeks0 = 0..MAXN;

   function jaotada(var a:jada; l,r:indeks):indeks;
       var i,j:indeks; b,x:liige;
       begin
        i:=l; j:=r; b:=a[l];
        repeat
            while a[i]<b do i:=i+1;
            while a[j]>b do j:=j-1;
            if i<j then
                begin
                   x:=a[i]; a[i]:=a[j]; a[j]:=x;
                   i:=i+1; j:=j-1;
                end;
        until i>=j;
        jaotada := j;
       end;

   procedure sort(var a:jada; n:indeks);
   {Antud: jarjend a[l] .. a[n]
    Tulemus: antud jarjend sorteeritud mittekahanevalt
    Algoritm: mitterekursiivne kiirmeetod
   }
       { --- Magasini kirjeldus staatilise struktuurina: --- }
       const MAXMAG = 10; { p.o. [1+(kahendlogaritm arvust MAXN)] }
       type rajad= record vasak, parem:indeks end;
            magasin= record
                           aken:indeks0;
                           elemendid: array [1..MAXMAG] of rajad
                     end;
       var M:magasin;
       {-------------------------------------------------- }



       {--------- Magasini protseduurid ------- }
       procedure TyhiMagasin(var M:magasin);
                 begin
                      M.aken := 0;
                 end;

       procedure PannaMagasini(var M:magasin; i:indeks; j:indeks);
                 begin
                   with M do
                   begin
                    if aken = MAXMAG then
                       begin
                            writeln('magasini yletaitumine');
                            exit
                       end;
                    aken := aken + 1;
                    elemendid[aken].vasak := i;
                    elemendid[aken].parem := j;
                   end;
                 end;

       procedure VottaMagasinist(var M:magasin; var i:indeks; var j:indeks);
       { Eeldus: magasin M ei ole tyhi }
                 begin
                   with M do
                   begin
                    i := elemendid[aken].vasak;
                    j := elemendid[aken].parem;
                    aken := aken - 1;
                   end;
                 end;
       function MagasinTyhi(var M:magasin):Boolean;
                begin
                     MagasinTyhi := (M.Aken = 0);
                end;
        {-------------------------------------- }

       var i,j,k:indeks; { abimuutujad }

       begin   { vt. algoritm lk. 11 }
          i := 1; j := n;
          TyhiMagasin(M);
          while(true)do
          begin
               { jaotatav osa on a[i] ... a[j] }
               while(i<j)do
               begin
                k := jaotada(a,i,j);
                if k-i <j-k then
                  begin { esimene osa (i .. k) on lyhem }
                     PannaMagasini(M,i,k);
                     i := k+1 { vaatlusele k+1 .. j }
                  end
                 else
                  begin { teine osa (k+1 .. j) on lyhem }
                     PannaMagasini(M,k+1,j);
                     j := k   { vaatlusele i .. k }
                  end
               end;
          if MagasinTyhi(M) then break;
          VottaMagasinist(M,i,j);  { uued osapiirid magasinist }
          end;
       end;