Shell sort is a sorting algorithm based on insertion sort. Insertion sort uses a fixed distance of 1 when it compares values during the sorting process. Insertion sort moves from left-to-right and picks the next value in the unsorted portion of the list and inserts it into its proper position in the sorted portion of the list. Shellsort uses a similar algorithm, but compares values over greater distances, called gaps. The benefit of comparing values over larger distances is that shell sort can quickly move small and large values to the front and end of the list, reducing the overall number of exchanges done by insertion sort. The final pass or gap used by shell sort is 1, which is insertion sort.

Shell Sort and Gap Sequence

There are a number of options for calculating the gap sequence used by shell sort. The last gap used by shell sort will be 1, which is insertion sort. In the Python algorithm used in this article the following formula is used to generate the gap sequence.

gaps = 2 * N / 2k+1 + 1, where k >= 1 and N is length of list

For a list of 10 items, the gap sequence will be 5, 3, 1.

Shell Sort Example

Let's say we have the following list to be sorted by shell sort.

[6, 0, 9, 3, 7, 5, 4, 1, 8, 2]

The first gap is 5 based on the gap formula. The list will be logically divided into several interleaved lists with a gap of 5, each one being sorted individually using the insertion sort algorithm. Logically these are 5 lists of 2 items each.

[6, 5] -> [5, 6]
[0, 4] -> [0, 4]
[9, 1] -> [1, 9]
[3, 8] -> [3, 8]
[7, 2] -> [2, 7]

After 5 sorting completes, this will be the new list.

After 5 sorting: [5, 0, 1, 3, 2, 6, 4, 9, 8, 7]

The same process occurs for a gap of 3 and 1.

After 3 sorting: [3, 0, 1, 4, 2, 6, 5, 9, 8, 7]
After 1 sorting: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

The final sort is insertion sort, which has a gap of 1.

Shell Sort in Python

Here is one solution for shell sort in Python. It's a little more complicated than insertion sort, because one has to caculate and keep track of the gaps used during the sorting process.

def shell_sort(lst):
    """
    Performs in-place Shell Sort on list of integers.
    
    :param lst: list of integers
    :return: None

    >>> lst = [6, 0, 9, 3, 7, 5, 4, 1, 8, 2]
    >>> shell_sort(lst)
    >>> assert(lst == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    """
    if lst is None or len(lst) < 2:
        return

    k = 1
    gap = len(lst)

    while gap > 1:
        gap = 2 * int(len(lst) / 2 ** (k+1)) + 1
        if gap < 1:
            gap = 1

        for index in range(len(lst) - gap):
            i = index + gap

            while i < len(lst):
                value = lst[i]
                j = i

                while j - gap > -1:
                    if value > lst[j-gap]:
                        break
                    lst[j] = lst[j-gap]
                    j -= gap

                lst[j] = value
                i += gap

            index += 1

        k += 1

Conclusion

Insertion sort is a very popular sorting algorithm, and shell sort is also used by various libraries. If you're interested in other sorting algorithms that use the gap technique for comparing values over larger distances, comb sort is a great example.

 

Posted by David Hayden

David Hayden is a freelance C# .NET MVC and JavaScript web developer. He is currently learning data structures and algorithms in computer science using Python and Java as well as learning data science and statistics using Python and R. You can find him on twitter as @koderdojo.

Related Posts: