Program Algorithm;

{ Shell's sort.
  Algorithm D on page 85 of "The Art of Computer Programming"
  volume 3 / "Sorting and Searching" by Donald E. Knuth
  See also his result (8) on page 95.
  Programmed as in: Turbo Pascal 7, The Complete Reference, page 700 }

const
  N = 100;
var
  rij : array[1..N] of word;
  m : word;

procedure ShellSort;

var
  i, j, h : integer;
  t, q, s : byte;
  r : word;

begin
  h := 1;
  t := 1;
  while h < N do
  begin
    t := t + 1;
    h := h*3 + 1;
  end;
  h := h div 3;
  t := t - 2;

  for q := 0 to (t-1) do
  begin
    s := t - q;
    h := h div 3;
    for j := (h+1) to N do
    begin
      i := j - h;
      r := rij[j];
      while i > 0 do
      begin
        if r >= rij[i] then Break;
        rij[i+h] := rij[i];
        i := i - h;
      end;
      rij[i+h] := r;
    end;
  end;
end;

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

begin
  m := Random(3*N)+1;
  for m := 1 to N do
  begin
    rij[m] := Random(3*N)+1;
  end;
  for m := 1 to N do
    Write(rij[m],' ');
  Writeln;

  ShellSort;

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