Shell Sort - Ravi's Notes

Background

Shell Sort is a faster form of insertion sort

The Shell Sort is considered one of the easier sorts to implement. The shell sort is a series of insertion sorts performed on sub-lists of the list to be sorted.

The basic idea in Shell Sort is to perform insertion sort on sub-lists comprised of elements whose index is separated by a gap value, for a series of gap values. By starting with large gap values, Shell Sort allows smaller elements that are out of place to move large distances across the list to be closer to their proper ordered position without shifting any intermediate elements. With each iteration, the gap is reduced, and the list becomes progressively more ordered.

In the final iteration, when the gap is reduced to 1, Shell Sort effectively performs a standard insertion sort—but by then, the list is already nearly sorted, so very little work remains to be done.

Gap Sequence

Before we go further into the shell sort, we need to understand the concept of the gap sequence. This is simply a sequence of numbers where we start at a certain number, and on each pass, we apply a gap formula to the current sequence value, to get the next sequence value. The gap formula could be something as simple as dividing the current gap value by 2. The only requirement is that the sequence should have the value 1 within it. The current value of the gap sequence is called the gap value. So the requirement is that one of the gap values generated by the gap sequence has to be 1. It doesn’t take a lot of intuition to determine why the number 1 is so important. A gap value of 1 signifies a normal and full insertion sort. Let us hold that thought for later.

How to pick a gap value

The start value of the current gap value (h) obviously has to be the less than the size of the list of elements being sorted.
The final gap value must be 1 to ensure that the array is fully sorted by running an insertion sort on the last iteration.
Gaps should be non-repeating and typically strictly decreasing.
Gaps should ideally be coprime with each other or vary non-trivially to break patterns.
They should allow for both coarse and fine comparisons (start large, shrink gradually).
The rate of decay matters: too steep → not enough work early; too slow → redundant passes.

Gap Sequence Generator Function

As with all sequences in math, the gap sequence is generated by a generator function. There is a whole range of functions that have been proposed. A more detailed discussion regarding the sequence generator functions can be found here.

Key Qualities of a good Gap Sequence Generator Function

A primary criterion that determines a good gap generator function is that the list should be nearly sorted by the time the sequence reaches 1. The sequence generated by the function must have the number 1 within it.

Gaps should be non-repeating and ideally co-prime with each other or at least not share many factors between themselves, or you risk missing out on sorting between some indexes until very late. The gaps are not required to be relatively prime though.

Optimal number of gaps to balance coverage and redundancy: The number of gaps generated by the sequence should be enough to allow for meaningful element comparisons across the list, but not so many that multiple iterations of sub-list insertion sorts are run by the shell sort with little effect on the disorder within the list, thereby wasting time.

The gaps should start large, and shrink gradually. The rate of shrinking of the gap matters – too steep -> not enough work early; too slow -> many redundant passes. Explained below.

Early gaps should be large..

The earlier gaps in the sequence should be large enough to allow elements to move large distances across the list (and therefore closer to their correct position within the list), thereby allowing smaller elements to move towards the beginning of the list and larger elements towards the end.

… but not too large relative to the size of the list

Too large gaps will create sub lists with very few elements. This leads to computationally intensive iterations that perform too few meaningful swaps because the gap is too large and elements too few to catch most inversions (element exchanges) which barely reorders the array, and leaves most of the sorting work for later iterations. This is not optimal and will tend the sort time complexity towards that of the standard insertion sort.

If the early gaps are too large and the gaps shrink too fast towards 1:

We end up fixing only a few far apart inversions and missing opportunities to fix mid-range disorder in the early iterations. This leaves a lot of work for the few later passes, and essentially the last pass (which is the insertion sort) ends up doing most of the work.

If the early gaps are too large and the gaps shrink too slowly towards 1:

Early on, you do low value iterations which leave much of the disorder in place and unhandled.
Overall you do too many passes, especially near the end when gaps are small and gap size tends towards 1.
You still pay the cost of traversing and sorting subarrays that aren’t very disordered.
The total runtime balloons because you’re doing too much shallow cleanup before the deep cleaning starts.

If the early gaps are too small, shell sort begins to resemble the plain insertion sort, negating the advantages of the Shell Sort over the insertion sort. Also, smaller early gaps mean you are missing out on the global repositioning efforts of the Shell Sort. The Shell Sort’s key advantage is that it lets elements jump long distances early, quickly reducing global disorder.

Far-apart inversions remain untouched until very late.
You need more swaps and comparisons in later passes.
The final insertion-sort-like phase ends up doing all the heavy lifting, affecting performance.

Property	Description
Starts with moderately large gaps relative to the size of the list being sorted.	Ensures distant swaps and rapid early progress
Shrinks geometrically or using optimized formulas	Avoids excessive passes, or too few early passes and leaving most of the work for later passes.
Avoids small early gaps	Prevents redundant early work, and reduces global disorder. Reducing global disorder is a primary advantage of the Shell Sort.
Ends with a gap of 1	Guarantees final pass is a true insertion sort, which is a mandatory requirement for a successful Shell Sort.

Example Gap Sequences and their pros and cons

The Insertion Sort algorithm used by the Shell Sort

In a regular insertion sort, starting with the 2nd element, we visit each element all the way to the last element of the list, and insert the visited element in its appropriate position in the sub-list that is composed of itself and all the elements to its left. The (usually unstated) condition here is that the gap between indexes of adjacent elements of a sub-list in the regular insertion sort is 1. This is why the sub-list is composed of all the elements to the left of the currently selected element in addition to the selected element itself.
In the shell sort, an insertion sort is run for each gap value generated by the gap sequence starting with a start gap value all the way down to a final gap value of 1. Remember that the start gap value has to be smaller than the size of the list of elements to be sorted.
In each iteration of the generalized insertion sort that is run by the shell sort, given the current gap value of h, we visit each element starting with the h^th element of the list all the way to the last element of the list, and insert the currently visited element in its appropriate position in the sub-list that is composed of itself and all the elements to its left (just like we do in insertion sort) whose indexes are separated from the currently visited element by a positive multiple of h (in standard insertion sort, h = 1). The distance between any two adjacent elements of this sub list is always h.
Eg: If the currently selected element has an index i and current gap value is h, then the sub-list will
be {A[i], A[i-h], A[i-2h], A[i-3h],A[i-4h]….A[i-kh]} such that i-kh >= 0 and k is a positive integer.
Note: If the currently selected element is already the greatest element in the sub-list, then it does not need to be moved.
In mathematical terms, given 2 elements of the sub-list with indexes i1 and i2, then |i1-i2| = kh where k is a positive integer. Regular insertion sort can be seen as a special case of the generalized insertion sort that is run by the shell sort where the gap value is 1 (h = 1).
When the current gap value reaches 1 (h = 1) on the last iteration of the shell sort, in effect a standard insertion sort is run over the list.

Sub-list selection: Reverse direction

A point of note is that in each iteration of the shell sort’s insertion sort which runs for a specific gap value h, the sub-lists are formed in the reverse direction starting with an end index i such that h ≤ i ≤ n (i ranges from h to the end of the list) where n is the last index of the list being sorted.

Sub-list selection: Forward direction sub-lists.

An alternate and helpful way to form a mental picture of the sub-lists formed for each iteration of the insertion sort run within the shell sort is to visualize them as forward direction sub-lists. Here i is the start index of each sub-list and 0 ≤ i ≤ h-1. (i ranges from 0 to h-1). h is the current gap value.

Eg: For a gap value h and a sub-list start index value of i, the sub-list will be: {A[i], A[i+h], A[i+2h], A[i+3h],A[i+4h]….A[i+kh]} such that i+kh < N where N is the size of the list and k is a positive integer. In other words, i + kh cannot exceed the size of the list.

Other Points about the insertion sort algorithm

With every iteration of the shell sort, the previous value in the gap sequence becomes the current gap value (h), continuing until h = 1, at which point a final insertion sort is performed on the full list. The gap value shrinks with each iteration, until it finally reaches the value of 1.

At the end of each iteration of the shell sort for a gap value h, the list is said to be h-sorted.

After each iteration, the list becomes progressively more sorted, making subsequent passes more efficient.

By the time the current gap value reaches the number 1, the multiple sub-list insertion sorts that have occurred previously ensure that the list is partially or almost fully sorted.

The Shell Sort Algorithm

Description

As described earlier, shell sort is essentially a set of insertion sorts run for a set of diminishing gaps determined by the gap generator function that goes from a start gap value h down to 1 where h < N (size of the list). This start gap value must be less than the size of the list.

For each gap value h, exactly h sub-lists are identified within the list and the list is insertion sorted in-place for that gap value using the identified sub-lists. One sub-list for each value of i where h ≤ i ≤ n. n is the last index of the list.

Let us call i as the marker index. Each sub-list is formed by grouping together elements within the list whose index value idx = (marker index i)-(k*h) where i = (h, h+1, h+2, h+3, h+4…..n) in other words, h ≤ i ≤ n. h is the current gap value, k is a whole number. k ϵ {0,1,2,3,4….} and n is the last index of the list.

For example: Given a list to be sorted A and i = (h, h+1, h+2, h+3. h+4…) then the first sub-list would be {A[h], A[h-h]} or {A[h], A[0]}, the second sub-list would be {A[h+1], A[h+1-h]} or {A[h+1], A[1]} (will also include A[0] if h=1) third sub list would be {A[h+2], A[h+2 -h]} or {A[h+2], A[2]} (will also include A[1] and A[0] if h=1) and so on.

All h sub-lists identified for a gap value are sorted in-place by moving elements within them to their correct position within the sub-list relative to the other elements of the sub-list. At the end of one iteration for a gap value h, the list is said to be h-sorted.
Once h has reached a value of 1, the list has been h-sorted for a number of gap values, and ideally should be close to fully sorted. At this point because h = 1, we are essentially running a regular insertion sort on the nearly sorted list. At the end of this iteration, the list has been fully sorted.

Implementation Steps:

Similar to insertion sort, we start with a value that we will call the marker index i, where starting value of i = h, the current gap value.
The marker index thus moves from h to n for each gap value – each value of h.
Given the current value of the marker index i and current gap value of h, we compare A[i] with all the elements in its sub-list (A[i-h], A[i-2h], A[i-3h]….) such that i-kh >= 0 and k is a positive integer. We then increment the marker index by 1 and repeat this step until the marker index reaches the end of the list.
We repeat the above step for each decreasing gap value all the way down to a gap value of 1.
At the end of the iteration for a specific gap value h, the overall list is said to be h-sorted where h is the gap’s current value.
This process is repeated until the gap value reaches 1 (h = 1), which means that the final iteration (with a gap size of 1) is a regular insertion sort.
Note that all of this is performed in-place on the list being sorted, which means that no additional space is allocated nor sub-lists created in memory.

Code Examples

Below is an example of what the actual code that implements the above algorithm looks like:

Python

 # Generate initial Knuth gap
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1  # 1, 4, 13, 40, ...

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp

        gap //= 3

# Example usage
arr = [37, 22, 0, -5, 19, 8, 45, 3]
shell_sort(arr)
print(arr)

def shell_sort(arr):
    n = len(arr)

Java

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // Generate initial Knuth gap: 1, 4, 13, 40, 121, ...
        int gap = 1;
        while (gap < n / 3) {
            gap = 3 * gap + 1;
        }

        // Perform Shell sort
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }

                arr[j] = temp;
            }

            gap /= 3;
        }
    }

    public static void main(String[] args) {
        int[] arr = {37, 22, 0, -5, 19, 8, 45, 3};
        shellSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

Shell sort is in many cases an improvement on insertion sort, which has a time complexity of O(N²). Shell sort complexity can range from best case: O(NlogN) to worst case: O(N²). Please see section on Gap Generator Functions to see the range of possible time complexities for the Shell Sort.

Additional Resources

See big O notation for a refresher on time complexity.