Author: Jonas Bilinkevicius

A Delphi implementation of the Shellsort algorithm

Answer:

1   function FirstLow(var A, B: Str64): Boolean;
2   begin
3     if A < B then
4       FirstLow := True
5     else
6       FirstLow := false;
7   end;
8   
9   procedure BinArraySort(Start, Finish: Integer; var Data: PosAry);
10  var
11    StarterKey: Str64;
12    Temp: PositionRec; {see remark below}
13    Left: Integer;
14    Right: Integer;
15  begin
16    Left := Start;
17    Right := Finish;
18    StarterKey := Data[(Start + Finish) div 2].PBStr;
19    repeat
20      while FirstLow(Data[Left].PBStr, StarterKey) do
21        Left := Left + 1;
22      while FirstLow(StarterKey, Data[Right].PBStr) do
23        Right := Right - 1;
24      if Left <= Right then
25      begin
26        Temp := Data[Left];
27        Data[Left] := Data[Right];
28        Data[Right] := Temp;
29        Left := Left + 1;
30        Right := Right - 1;
31      end;
32    until
33      Right <= Left;
34    if Start < Right then
35      BinArraySort(Start, Right, Data);
36    if Left < Finish then
37      BinArraySort(Left, Finish, Data);
38  end;
39  
40  //Remark:
41  
42  PositionRec = record
43    PBStr: Str64; {key}
44    {additional fields}
45  end;
46  
47  PosAry = array[1..??] of PositionRec;
48  PosAryPtr = ^PosAry


is better than just the array itself. Then:

procedure BinArraySort(Start, Finish: Integer; Data: PosAryPtr);

The caller:

49  var
50    PA: PosAryPtr;
51  begin
52    BinArraySort(1, BItems, PA);