Shell Sort

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 of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 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