# Shell sort

From Lazarus wiki

│
**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

- Karen Van Houten, Shell Sort, University of Idaho. Archived at Wayback Machine.