## 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 < a[4-4] | a < a | 2 < 0 | False
j = 0

i = 5
j = 5
a  < a[5-4] | a < a | 5 < 1 | False
j = 1

array = [1,0,3,4,2,5]

h = 1
i = 1
j = 1
a < a[1-1] | a < a | 0 < 1 | True
a = 0
a = 1
array = [0,1,3,4,2,5]
j = 0

i = 2
j = 2
a < a[2-1] | a < a | 3 < 1 | False
j = 1
a < a[1-1] | a < a | 1 < 0 | False
j = 0

i = 3
j = 3
a < a[3-1] | a < a | 4 < 3 | False
j = 2
a < a[2-1] | a < a | 3 < 1 | False
j = 1
a < a[1-1] | a < a | 1 < 0 | False
j = 0

i = 4
j = 4
a < a[4-1] | 2 < 4 | True
a = 2
a = 4
array = [0,1,3,2,4,5]
j = 3
a < a[3-1] | 2 < 3 | True
a = 2
a = 3
array = [0,1,2,3,4,5]
j = 2
a < a[2-1] | 2 < 1 | False
j = 1
a < 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

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