# Shell Sort

This algorithm is based on Insertion Sort but instead of starting the comparison between adjacent elements it introduces the notion of a gap.

On simple implementations the gap is just N/2 meaning that it starts comparing elements separated by N/2 elements. For example if we have an array with 10 elements, the first comparison will be between element on index the 5 and element on the index 0. If elements are not sorted an exchange occurrs. If they are, the algorithm moves to the next elements (on indexes 6 and 1). Notice that the gap of 5 continues until the end of the array. After that, the gap equals the value of the last gap divided by 2 again. New gap is 2 (5/2). Then we start again, comparing indexes 2 and 0, 3 and 1, 4 and 2, etc. Please notice that on this last comparison (4 and 2) if element on index 4 was smaller than the one on index 2 the algorithm would also compare the element with the element on the index 0 (keeping a gap of 2).

After a gap of 2 comes the gap of 1. After this last gap (of 1), we can say that the array is sorted.

I’ll show you the code.

```
def shell_sort(l):
n = len(l)
gap = n / 2
while gap > 0:
i = 0
while gap + i < n:
temp = l[gap + i]
j = i
while temp < l[j] and j >= 0:
l[j + gap] = l[j]
j -= gap
l[j + gap] = temp
i += 1
gap /= 2
```

```
l = [33, 32, 3, 45, 5, 6, 8, 0, 99, 72, 14]
shell_sort(l)
print l # [0, 3, 5, 6, 8, 14, 32, 33, 45, 72, 99]
```