--- ---

Shell Sort is really just an extension of Insertion Sort, with two observations in mind:

- Insertion Sort is efficient if the input is "almost sorted".
- Insertion Sort is inefficient, on average, because it moves values just one position at a time.

Shell Sort is similar to Insertion Sort, but it works by taking "bigger steps" as it rearranges values, gradually decreasing the step size down towards one. In the end, Shell Sort performs a regular Insertion Sort but by then, the array of data is guaranteed to be "almost sorted".

Consider a small value that is initially stored in the wrong end of the array. Using Insertion Sort, it will take roughly N comparisons and exchanges to move this value all the way to the other end of the array. With Shell Sort, we'll first move values using giant step sizes, so a small value will move a long way towards it's final position, with just a few comparisons and exchanges.

    procedure SortShell(var aSort: array of Word);
    var
      iI, iJ, iK,
      iSize: Integer;
      wTemp: Word;
    begin
      iSize := High(aSort);
      iK := iSize shr 1;
      while iK > 0 do begin
        for iI := 0 to iSize - iK do begin
          iJ := iI;
          while (iJ >= 0) and (aSort[iJ] > aSort[iJ + iK]) do begin
            wTemp := aSort[iJ];
            aSort[iJ] := aSort[iJ + iK];
            aSort[iJ + iK] := wTemp;
            if iJ > iK then
              Dec(iJ, iK)
            else
              iJ := 0
          end;
        end;
        iK := iK shr 1;
      end;
    end;

## Demo code

A ready made project containing this demo code is available. View the project.

This demo creates a list of random numbers and displays them in a list box. It then sorts the numbers using SortShell and displays the sorted list in a second list box.

Create a new Delphi VCL project and drop two TListBox controls on it. Also create an OnCreate event handler for the form. Name the form "Form1" and save the form unit as `Unit1.pas`.

Code Unit1 as follows:

    unit Unit1;

    interface

    uses
      SysUtils, Forms, Classes, Controls, StdCtrls;

    type
      TForm1 = class(TForm)
        ListBox1: TListBox;
        ListBox2: TListBox;
        procedure FormCreate(Sender: TObject);
      end;

    var
      Form1: TForm1;

    implementation

    {$R *.dfm}

    // Routine from tip
    procedure SortShell(var aSort: array of Word);
    var
      iI, iJ, iK,
      iSize: Integer;
      wTemp: Word;
    begin
      iSize := High(aSort);
      iK := iSize shr 1;
      while iK > 0 do begin
        for iI := 0 to iSize - iK do begin
          iJ := iI;
          while (iJ >= 0) and (aSort[iJ] > aSort[iJ + iK]) do begin
            wTemp := aSort[iJ];
            aSort[iJ] := aSort[iJ + iK];
            aSort[iJ + iK] := wTemp;
            if iJ > iK then
              Dec(iJ, iK)
            else
              iJ := 0
          end;
        end;
        iK := iK shr 1;
      end;
    end;

    procedure TForm1.FormCreate(Sender: TObject);

      procedure AddToLB(const Nums: array of Word; LB: TListBox);
      var
        I: Integer;
      begin
        for I := Low(Nums) to High(Nums) do
          LB.Items.Add(IntToStr(Nums[I]));
      end;

    var
      I: Integer;
      Nums: array[1..50] of Word;
    begin
      // Create list of random numbers and display it
      Randomize;
      for I := Low(Nums) to High(Nums) do
        Nums[I] := Random(1000);
      AddToLB(Nums, ListBox1);
      // Sort list and display sorted numbers
      SortShell(Nums);
      AddToLB(Nums, ListBox2);
    end;

    end.

Demo by Peter Johnson