# Difference between revisions of "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. The algorithm was published in assembler code by Donald L. Shell in 1959.

## 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);
```