Program Algorithm;

{ Straight insertion sort.
  Algorithm S on page 81 of "The Art of Computer Programming"
  volume 3 / "Sorting and Searching" by Donald E. Knuth }

const
  LIM = 100;

var
  n : word;
  rij : array[1..LIM] of word;

{ *********************** }

procedure Straight;

var
  m, k, L, g : word;

begin
  for m := 2 to LIM do
  begin
    g := rij[m];
    if g >= rij[m-1] then Continue;
    for k := 1 to (m-1) do
    begin
      if g < rij[m-k] then
        rij[m-k+1] := rij[m-k]
      else Break;
      L := k;
    end;
    rij[m-L+1] := rij[m-L];
    rij[m-L] := g;
  end;
end;

{ *********************** }

begin
  n := Random(5*LIM)+1;
  for n := 1 to LIM do
  begin
    rij[n] := Random(5*LIM)+1;
  end;
  for n := 1 to LIM do
    Write(rij[n],' ');
  Writeln;

  Straight;

  for n := 1 to LIM do
    Write(rij[n],' ');
  Writeln;
end.