Shell sort algorithm

Shell Sort Algorithm:-

Shell sort algorithm is an improved version of Insertion sort algorithm. In an average case when list is already partially sorted insertion sort is not an efficient way to solve the problem. Thus, we use shell sort algorithm.

        In shell sort algorithm, we divide the list in no. of lists according to the length of the list and then apply insertion sort on each sub-list. And then merge all the sub-lists to form one.

Example:-

       0   1   2   3  4   5   6    7     8   9  10

     70 30 40 10 80 20 90 110 75 60 45

We can divide it into 3 parts with 2 having 4 elements and one having 3 elements.

       0       3      6     9                 1       4     7        10                 2     5     8

    70 10 90 60         30 80 110 45          40 20 75

Apply insertion sort on each sub-list.

     0       3      6      9                1     4        7     10                  2      5     8

    10 60 70 90         30 45 80 110          20 40 75 

Merge them.

     0   1   2   3  4   5   6    7     8   9  10

    10 30 20 60 45 40 70 80 75 90 110

Divide it into two parts.

     0   2   4    6   8   10                1  3   5   7   9  

    10 20 45 70 75 110              30 60 40 80 90

Sort them using insertion sort.

      0   2    4   6   8   10                 1   3  5    7   9

     10 20 45 70 75 110               30 40 60 80 90

Merge them.

      0    1   2    3  4  5   6   7   8  9     10

     10 30 20 40 45 60 70 80 75 90 110 

Apply insertion sort to the list.

        10 20 30 40 45 60 70 75 80 90 110                

The list is sorted now.