How ShellSort works

ShellSort is the last sorting algorithm in my sorting series. Shellsort is a sorting method, which works in-place. ShellSort is the extension of or based on InsertionSort.

In the best case, the procedure has an effort $O(n)$, if the list is already sorted. In the average and worst case, each has an effort $O(n(Log(n))^2)$ to O(n^2), depending on the choice of the sequence for the distance and size of the list.

How does ShellSort work?

ShellSort gets an unsorted list. First the length of the list is determined and halved. The result is our gap size. In the example I take the naive gapsize $\frac{n}{2}$. I take my first element from the list, in the distance of the gapsize, I take the 2nd element. I do this until I have completely wandered over the list. Here you should make sure that each element is only selected with one other element. If an element cannot be linked with any other element, it will be ignored. After all links are made, we go through all of them and compare the left element with the right element. The smaller element is always on the left. When we have reached a gap size of 1, we run through with InsertionSort.

A small sketch, illustrates how Shellsort works.

If we now look at the implementation in Python, we see striking places that remind us of InsertionSort.

#!/usr/bin/env python
import random

class ShellSort(object):

    def __init__(self):
        None

 def sort(self, array):
    gap = len(array) / 2
    while(gap > 0):
        temp = j = 0;
        for walker in range(gap, len(array)):
            j = walker
            while((j > 0) and (array[j - 1] > array[j])):
                temp = array[j -1];
                array[j - 1] = array[j];
                array[j] = temp;
                j -= 1;
        gap /= 2
    return array

if __name__ == '__main__':
    array = []
    for i in range(0, 10000):
        array.append(random.randint(0, 100))


    ss = ShellSort()
    print "unsorted" , array
    print "sorted", ss.sort(array)

We see that our distance gap is half of our list length. We let the gap run towards 0, and then apply the modified InsertionSort. InsertionSort normally starts at the 2nd element of the list. Here InsertionSort starts at our gap distance. The inner part of ShellSort works the same way as InsertionSort. After each pass of our InsertionSort, the distance gap is halved. At a distance of 1 we have our InsertionSort again.

The choice of the sequences.

To simply set the distance to $\frac{N}{2}$ is a bad choice, because we reach an effort of $O(n^2)$. But if we work with the Hibbard sequence, we achieve a lower effort.

The Hibbard sequence is : $2^k -1 \rightarrow [0, 1, 3, 7, 15, 31...]$

I hope I could give a little insight to ShellSort 😄