Shell Sort

• The shell sort, sometimes called the “diminishing increment sort,” improves on the insertion sort by breaking the original list into a number of smaller sublists, each of which is sorted using an insertion sort. 

• The unique way that these sublists are chosen is the key to the shell sort. 

• Instead of breaking the list into sublists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sublist by choosing all items that are i items apart.

Algorithm:

Step1: Initialise the value of d

Step 2: Divide the list into smaller sub-list of equal interval d

Step 3: Sort these sub-list using insertion sort

Step 4: Repeat until complete list is sorted 

Example:

we take the interval of 4. Make a virtual sub-list of all values located at the interval of 4 positions. d=4

Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}

We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this −

Then, we take interval of 1 and this gap generates two sub-lists - {14, 27, 35, 42}, {19, 10, 33, 44}

We compare and swap the values, if required, in the original array. After this step, the array should look like this −

Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array.

Time Complexities:

• Worst Case Complexity: O(n2))
  If we want to sort in ascending order and the array is in descending order then, the worst case occurs.

• Best Case Complexity: O(n log(n))
  It occurs when the array is already sorted

• Average Case Complexity: O(n log(n))
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending)