# Shell sort

## Algorithm

The main idea behind the algorithm is that starting anywhere, taking the `h`

-th entry yields a sorted subsequence.
We will implement an algorithm that takes values for `h`

from the sequence `(1/2)(3^k - 1)`

. This gives us the sequence 1,4,13,40… that will be called the `increment sequence`

.

```
def shell(a):
"""
Implements the shell sort algorithm. It is a variant of the insertion algorithm.
"""
# Compute the increment sequence
h = 1
while h < (len(a) / 3):
h = 3*h + 1
# Sort
while h >= 1:
for i in range(h, len(a)):
j = i
while j >= h:
if a[j] < a[j-h]:
temp = a[j]
a[j] = a[j-h]
a[j-h] = temp
j = j-h
h = h/3
return a
```

## Step by step

```
array = [1,0,3,4,2,5]
h = 1
len(array) = 6
h = 1 | h < 2 | True
h = 4 | h < 2 | False
h = 4
i = 4
j = 4
a[4] < a[4-4] | a[4] < a[0] | 2 < 0 | False
j = 0
i = 5
j = 5
a [5] < a[5-4] | a[5] < a[1] | 5 < 1 | False
j = 1
array = [1,0,3,4,2,5]
h = 1
i = 1
j = 1
a[1] < a[1-1] | a[1] < a[0] | 0 < 1 | True
a[1] = 0
a[0] = 1
array = [0,1,3,4,2,5]
j = 0
i = 2
j = 2
a[2] < a[2-1] | a[2] < a[1] | 3 < 1 | False
j = 1
a[1] < a[1-1] | a[1] < a[0] | 1 < 0 | False
j = 0
i = 3
j = 3
a[3] < a[3-1] | a[3] < a[2] | 4 < 3 | False
j = 2
a[2] < a[2-1] | a[2] < a[1] | 3 < 1 | False
j = 1
a[1] < a[1-1] | a[1] < a[0] | 1 < 0 | False
j = 0
i = 4
j = 4
a[4] < a[4-1] | 2 < 4 | True
a[3] = 2
a[4] = 4
array = [0,1,3,2,4,5]
j = 3
a[3] < a[3-1] | 2 < 3 | True
a[2] = 2
a[3] = 3
array = [0,1,2,3,4,5]
j = 2
a[2] < a[2-1] | 2 < 1 | False
j = 1
a[1] < a[1-1] | 1 < 0 | False
j = 0
i = 5
j = 5
... | False
j = 4
... | False
j = 3
... | False
j = 2
... | False
j = 1
... | False
j = 0
h = 0
array = [0,1,2,3,4,5]
```

## Complexity analysis

### Time

O(N) = N^(3/2)

### Space

We use the same array that is passed as argument and a few more variables, so the cost is: O(N) = N + K ≈ N.

## Use cases

- Large arrays
- Arrays that are in arbitrary order