{ K A H E N D P I S T E M E E T O D }



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

   function lisamiskoht(var a:jada; i:indeks): indeks;
   {Antud:   jada a[1..i], a[1..i-1] on sorteeritud
    Tulemus: tagastatakse liikme indeks, mille ette sobib lisada a[i]}
       var j:indeks; {otsimisvahemiku algus}
           m:indeks; {otsimisvahemiku lopp}
           k:indeks; {otsimisvahemiku keskkoht}
           tulemus: indeks0;
       begin
           j:=1; m:=i-1; {otsimisvahemik algselt}
           tulemus := 0;
           while (tulemus = 0) do {kuni lisamiskoht saab leitud}
                 begin
                      k:= (j+m) div 2; {otsimisvahemiku keskkoht}
                      if (a[k] = a[i]) then {kui keskmine liige = a[i]}
                         tulemus := k;
                      {muuta otsimisvahemik: }
                      if (a[k] > a[i]) then m := k-1 else j := k+1;
                      if (m < j) then {kui otsimisvahemik on tyhi}
                         tulemus := j;
                 end;
           lisamiskoht := tulemus;
       end;
   procedure paigutada(var a:jada; i:indeks; pistekoht: indeks);
   {Antud: jada a[1..i] ja pistekoht (liikme indeks, mille ette sobib a[i])
    Tulemus: liikmed a[pistekoht .. i-1] nihutatud koha vorra paremale ja
             liige a[i] salvestatud kohale a[pistekoht]}
       var b: liige; j: indeks;
       begin
           b:=a[i];    {liige a[i] "meelde"}
           for j:=i-1 downto pistekoht do a[j+1] := a[j]; {nihutamine}
           a[pistekoht] := b; {salvestada "meeles" olev liige}
       end;
   procedure sort(var a:jada; n:indeks);
   {Antud: jarjend a[1] .. a[n]
    Tulemus: antud jarjend sorteeritud mittekahanevalt kahendpistemeetodil
    Kasutatakse:
       funktsioon 'lisamiskoht' - vaadeldavale liikmele pistekoha leidmiseks
       protseduur 'paigutada' - vaadeldava liikme "pistmiseks" leitud kohale}
       var i:indeks;
       begin
          for i:=2 to n do  paigutada(a,i,lisamiskoht(a,i));
       end;



                                     9