Shell sort is a sorting algorithm that is based on the insertion sort algorithm. If the smaller value is on the far right and must be relocated to the far left, this technique avoids huge shifts as in insertion sort.

This algorithm employs insertion sort on widely distributed elements, first sorting them and then sorting the less widely distributed elements. This space is known as an interval. Based on Knuth’s formula, this interval is calculated as :

### Knuth’s Formula

h = h * 3 + 1 where − h is interval with initial value 1

This approach is quite efficient for medium-sized data sets because the average and worst-case complexity of this algorithm is O(n), where n is the number of elements. In addition, the worst-case space complexity is O. (n).

### Algorithm

Following is the algorithm for shell sort.

Step 1− Initialize the value ofhStep 2− Divide the list into smaller sub-list of equal intervalhStep 3− Sort these sub-lists usinginsertion sortStep 3− Repeat until complete list is sorted

## Pseudocode

Following is the pseudocode for shell sort.

procedure shellSort() A : array of items /* calculate interval*/ while interval < A.length /3 do: interval = interval * 3 + 1 end while while interval > 0 do: for outer = interval; outer < A.length; outer ++ do: /* select value to be inserted */ valueToInsert = A[outer] inner = outer; /*shift element towards right*/ while inner > interval -1 && A[inner - interval] >= valueToInsert do: A[inner] = A[inner - interval] inner = inner - interval end while /* insert the number at hole position */ A[inner] = valueToInsert end for /* calculate interval*/ interval = (interval -1) /3; end while end procedure