Shell Sort

Shell sort is a generalized version of the insertion sort algorithm. It first sorts elements that are far apart from each other and successively reduces the interval between the elements to be sorted.

The interval between the elements is reduced based on the sequence used. Some of the optimal sequences that can be used in the shell sort algorithm are:

• Shell’s original sequence: N/2 , N/4 , …, 1
• Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
• Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1
• Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Papernov & Stasevich increment : 1, 3, 5, 9, 17, 33, 65,...
• Pratt : 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

Note: The performance of the shell sort depends on the type of sequence used for a given input array.

Shell Sort Algorithm

shellSort(array, size)
  for interval i <- size/2n down to 1
    for each interval "i" in array
        sort all the elements at interval "i"
end shellSort

Shell Sort Code in Python

def shellSort(array, n):
    interval = n // 2
    while interval > 0:
        for i in range(interval, n):
            temp = array[i]
            j = i
            while j >= interval and array[j - interval] > temp:
                array[j] = array[j - interval]
                j -= interval
array[j] = temp
        interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)