Intro: Shellsort is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange/insertion sort. The method starts by sorting pairs of elements far apart from each other, then reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange.It is mainly a variation of Insertion Sort where we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow the exchange of far items. Here we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.
Since it is based on shell sort, this algorithm avoids large shifts as in the case of insertion sort, if the smaller value is to the far right and has to be moved to the far left.


Initialize the value of h
Divide the list into smaller sub-list of equal interval h
Sort these sub-lists using insertion sort
Repeat until complete list is sorted

Pseudo Code:

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
            a[j] = a[j - gap]
        # put temp (the original a[i]) in its correct location
        a[j] = temp