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]