SHELL SORT

• Shell sort works by comparing elements that are distant rather than adjacent element in an array (or) list where adjacent elements are compared.
• Shell sort uses an increment sequence.
• The increment size is reduced after each pass until the increment size is 1.

 EXAMPLE
        

• n=length of the list=8
• Increment=n/2=8/2=4

Initial segmenting gap=4

We take the interval of 4.Make a virtual sub_list of all values located at the interval of 4 positions.Here these values are {18,38},{32,33},{12,16}and{5,2). 

We compare values in each sub_list and swap them in the original array.

Resegmenting gap=2

Then,we take interval of 2 and this gap generates two sub_lists {18,12,38,16},{32,2,33,5}.

We compare and swap the values,

Resegmenting gap=1

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

after the insertion sort we get the answer like this,

Shellsort Best case:

• The best case in the shell sort is when the array is already sorted in the right order.the no.of comparisons is less.

Shellsort worst case:

• The running time of shellsort depends on the choice of increment sequence.
• The problem with shell's increments is that pairs of increments are not necessarily relatively prime and smaller increments can have little effect.

Advantages:

• It's only efficient for medium size lists.For bigger lists, the algorithm is not the best choice.
• 5 times faster than the bubble sort & a litter over twice as fast as the insertion  sort.

Disadvantages:

• It is a complex algorithm & its not nearly as efficient as the merge,heap & quick sort.
• The shell sort is still significantly slower than the merge,heap & quick sorts.

        Also Refer INSERTION SORT                       

                                  ******