Universal fast "Shell" sort function.

[VirtualTT]

This function provides Ascending / Descending sorting using Shell algorithm. Relatively fast and can be easily adopted to be used with any kind of arrays.
(much faster compared with quick sort with medium arrays, may be slower in case of larger arrays(>1000 items), but always overcomes it in worst cases)

Here is the function code with some testing procedure:

Code: (pascal) [Select]

const
_asc = 1;
_des = -1;

procedure ShellSort(Direction: integer; var ArrayToBeSorted: array of integer);
var
buf: integer;
i, j, n, k: integer;
begin
k := GetArrayLength(ArrayToBeSorted);
n := k - 1;
k := k shr 1;
while (k > 0) do begin
i := 0;
while (i <= n-k) do begin
j := i;
while (j >= 0) and ((ArrayToBeSorted[j] - ArrayToBeSorted[j + k]) * Direction > 0) do begin
buf := ArrayToBeSorted[j];
ArrayToBeSorted[j] := ArrayToBeSorted[j+k];
ArrayToBeSorted[j + k] := buf;
if (j > k) then dec(j, k) else j := 0;
end;
inc(i, 1);
end;
k := k shr 1;
end;
end;

procedure ActivateServer();
var
t: array of integer;
i: integer;
TestArraySize: integer;
begin
TestArraySize := 50;
setarraylength(t, TestArraySize);
WriteLn('Array of random numbers:');
for i := 0 to TestArraySize-1 do begin
t[i] := Random(-30000, 30000);
WriteLn(IntToStr(t[i]));
end;
WriteLn('Ascending sorting:');
ShellSort(_asc, t);
for i := 0 to TestArraySize-1 do begin
WriteLn(IntToStr(t[i]));
end;
WriteLn('Descending sorting:');
ShellSort(_des, t);
for i := 0 to TestArraySize-1 do begin
WriteLn(IntToStr(t[i]));
end;
end;

[DarkCrusade]

This doesn't look like ShellSort.. I thought ShellSort was creating a pseudo-matrix and sort each row of the matrix one by one? I thought that if you use right shift on a variable it cannot be negative, too.. Could you clear things up?

[VirtualTT]

1. This is the Shell Sort. It's all about comparing and swapping items that are located far from each other so the array will move towards sorted state faster. In this case i'm using half of the array size as the starting gap between items to be compared. At the each iteration step this gap is being decreased and in the end degradates into comparison of the neighbor items at the last step. Iterations can be represented as sorting a column of a matrix which width is equal to the comparison gap and which is filled with the elements of the array being sorted. But actually no matrix is being created. There are also several methods to optimize gap calculation, but i just used plain one.
2. The result of using left shift is always equal to multiplication on 2, and the result of using right shift is always equal to division on 2. And whether value is positive or negative doesn't matter. But shift operations are supposed to be a bit faster than using *2 or /2.

[DarkCrusade]

That helped. Thanks!