procedure sort( var r : ArrayToSort; lo, up : integer );

     var  iwk : ArrayIndices;
          out : ArrayToSort;
          tempr : ArrayEntry;
          i, j : integer;
          flag : boolean;
     begin

     iwk[lo] := lo-1;
     for i:=lo+1 to up do iwk[i] := 0;
     for i:=lo to up do begin
          j := phi( r[i].k, lo, up );
          iwk[j] := iwk[j]+1
          end;
     for i:=lo to up-1 do iwk[i+1] := iwk[i+1] + iwk[i];
     for i:=up downto lo do begin
          j := phi( r[i].k, lo, up );
          out[ iwk[j] ] := r[i];
          iwk[j] := iwk[j]-1
          end;
     for i:=lo to up do r[i] := out[i];
     {*** Linear-insertion sort phase ***}
     for i:=up-1 downto lo do begin
          tempr := r[i];
          j := i+1;
          flag := true;
          while (j<=up) and flag do
               if tempr.k > r[j].k then begin
                    r[j-1] := r[j];
                    j := j+1
                    end
               else flag := false;
          r[j-1] := tempr
          end;
     end;