# Shell Sort

## Algorithm description

Shellsort is a simple extension of insertion sort which gains speed by allowing exchanges of elements that are far apart. The idea is to rearrange the array to give it the property that every hth element (starting anywhere) yields a sorted array. Such an array is said to be h-sorted.

By h-sorting for some large values of h, we can move elements in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values h which ends in 1 will produce a sorted array.

## Algorithm implementation

``` 1  subtype index is positive range 1..N;
2  type sort_array is array(index) of integer;
3
4  procedure shellsort (arr: in out sort_array)
5  is
6      N    : index   := arr'LENGTH;
7      v, k : integer;
8      h    : integer := 1;
9  begin
10
11      -- build the first h value
12
13      discrete h1 := 1 in 1..N
14          new h1 := 3*h1+1
15      loop
16          h1 := 3*h1+1;
17          h := h1;
18      end loop;
19
20      -- h-sort the array for h = ..., 121, 40, 13, 4 and finally 1
21
22      discrete i := h in reverse 2..h
23          new i := i/3
24      loop
25          i := i/3;
26
27          for j in i+1..N loop
28              v := arr(j);
29              k := j;
30
31              discrete l := k-i in reverse 1..k-i
32                  new l := l-i
33              loop
34                  if arr(k-i) <= v then
35                      exit;
36                  end if;
37                  arr(k) := arr(k-i);
38                  k := k-i;
39                  l := l-i;
40                  if k <= i then
41                      exit;
42                  end if;
43              end loop;
44              arr(k) := v;
45          end loop;
46      end loop;
47  end shellsort;
```

## Notes on design

In our implementation, we use the increment sequence

hM = 1, hM-1 = hM * 3 + 1

which yields the following sequence:

..., 1093, 364, 121, 40, 13, 4, 1

The first discrete loop (lines 13 to 18) is used to calculate the first value of h. (In fact, because the discrete loop is exited when the value of h1 is greater than N, it has to be divided by 3 to get the starting h).

The second discrete loop runs over the above introduced increment sequence and performs the h-sorting of the array. (By building the new value of the loop variable immediately in the first statement of the loop body, we skip the first value in the increment sequence which is anyway to high, as mentioned above.)

## Worst Case Performance

Let us begin with a quote from Sedgewick's Algorithms [Sed88]:

[...] no one has been able to analyze the algorithm. [...] Not even the functional form of the running time for Shellsort is known.

But nevertheless, Sedgewick proposes the following property:

Shellsort never does more than N3/2 comparisons (for the above used increment sequence).

## Selected Bibliography

[Ott93, p. 88] [Sed88, p. 107]