This sorting algorithm is conceived by D. L. Shell (that's where it gets its name), and is inspired by the Insertion Sort's ability to work very fast on an array that is almost in order. It is also called diminishing increment sort.

Unlike Insertion Sort, Shell Sort does not sort the entire array at once. Instead, it divides the array into noncontiguous segments, which are separately sorted by using Insertion Sort. Once all of the segments are sorted, Shell Sort redivides the array into less segments and repeat the the algorithm until at last that the number of segment equals one, and the segment is sorted.

There are two advantages of Shell Sort over Insertion Sort.

1. When the swap occurs in a noncontiguous segment, the swap moves the item over a greater distance within the overall array. Insertion Sort only moves the item one position at a time. This means that in Shell Sort, the items being swapped are more likely to be closer to its final position then Insertion Sort.
2. Since the items are more likely to be closer to their final position, the array itself becomes partially sorted. Thus when the segment number equals one, and Shell Sort is performing basically the Insertion Sort, it will be able to work very fast, since Insertion Sort is fast when the array is almost in order.

There are variations of Shell Sort depending on the method of arranging segments. The method that we will be studying here is called "2X". This method determines the number of segments by dividng the number of cells by two (integer division), so that in the first round each segment will have mostly two, and maybe two cells. After the first round, we decrease the number of segments by dividing them by two again. This is to be repeated until there are one segment left (the entire array). Think on what other ways we can divide the segments that can be more efficient.

Below is Shell Sort's pseudo-code.

Shell Sort (Sorting the array A[size])

    Determine the number of segments by dividing the number of cells by two.
    While the number of segments are greater than zero
    {
        For each segment, we do an Insertion Sort.
        (think on how to write the loops here efficiently... )
        Divide the number of segments by two.
    }