Shell sort

│ English (en) │

The shell sort algorithm (aka shellsort or Shell's sort) is an integer sorting algorithm. It is a fast sorting algorithm (although slower than quicksort) that has the advantage that it is non-recursive, so it doesn't use the call stack. Therefore the method is advantageous on small and embedded systems and for sorting very large arrays.

Features

• Very fast
• Doesn't need the call stack

unit UShellSort.pas

unit UShellSort;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  TShellSortItem = integer;

procedure ShellSort(var a: array of TShellSortItem);

implementation

procedure ShellSort(var a: array of TShellSortItem);
var i, j, h, n, v : integer;
begin
  n := length(a);
  h := 1;
  repeat
   h := 3*h + 1
  until h > n;
  repeat
   h := h div 3;
   for i := h + 1 to n do
    begin
     v := a[i];
     j := i;
     while (j > h) AND (a[j-h] > v) do
      begin
        a[j] := a[j-h];
        j := j - h;
      end;
     a[j] := v;
    end
   until h = 1;
end;

end.

Example of the use

uses
  UShellSort

  ...

var

  a: array[0..100] of integer; 


begin

  ...

  ShellSort(a);

References

• Shell, D. L. (1959). A High-Speed Sorting Procedure (PDF). Communications of the ACM. 2 (7): 30–32. doi: 10.1145/368370.368387.
• Karen Van Houten, Shell Sort, University of Idaho. Archived at Wayback Machine.