Сортировка методом Шелла

Аналогична сортировке "пузырьком" с просеиванием, исходный массив разбивается на подмассивы с определённым шагом, каждый из которых сортируется независимо, далее уменьшается шаг, и повторяется до того как шаг не станет меньше 0.

Const
 N=1000;
Type
 tarr=array[1..N] of integer;
Var
 arr : tarr;
 b : boolean;
 k,shag,i,j,tmp : integer;

...............................

shag:=N div 2;
While shag > 0 do
 Begin
  For j:=1 to (N-shag) do
   Begin
    k:=j;
    Repeat
     b:=false;
     if arr[k] < arr[k+shag] then
      Begin
       tmp:=arr[k];
       arr[k]:=arr[k+shag];
       arr[k+shag]:=tmp;
       k:=k-shag;
       b:=true;
      end;
    Until (k <= 1) and b;
   end;
  shag:=shag div 2;
 end;