Shell Sort

Steps:
This is improved version of insertion sort.
In insertion sort, we start from 1st index and compare each and every element with its previous adjacent element.

In Shell Sort also, we do the same.

But it is a repetitive Insertion Sort.

We select the gap and keep on performing insertion sort.
First we select gap as: len/2 = 4
then perform insertion sort at this gap*i indices(for example: if gap=4, we compare (4, 0), (5, 1), (6, 2), (7, 3)

Now divide the gap again by 2 ==> gap = gap/2 = len/4 = 2
Now comparisons are:
(2, 0), (3, 1), (4, 2), (5, 3), (6, 4), (7, 5)

Now divide the gap again by 2 ==> gap = gap/2 = len/8 = 1
Now comparisons are: (1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6)

Here we can observe that the last step is same as the Insertion Sort, but by this step the array is almost sorted, so there will be less number of swap operations.

Code:
import java.util.Arrays;

class ShellSort {
        static public void shellSort(int[] in) {
                int len = in.length;

                for(int gap = len/2; gap > 0; gap = gap/2) {
                        System.out.println("Gap=" + gap);

                        for(int i=gap; i<len; i++) {
                                int key = in[i];

                                int j = i;

                                while(j>=gap && in[j-gap] > key) {
                                        in[j] = in[j-gap];
                                        j = j-gap;
                                }

                                in[j] = key;
                        }
                }
        }

        static public void main(String[] args) {
                int[] in = {6, 8, 1, 4, 5, 3, 7, 2};

                System.out.println(Arrays.toString(in));

                shellSort(in);

                System.out.println(Arrays.toString(in));
        }
}

eg:

6 8 1 4 5 3 7 2

Gap=4
index=4, key=5
index=5, key=3
index=6, key=7
index=7, key=2

Sorted:[5, 3, 1, 2, 6, 8, 7, 4]

Gap=2
index=2, key=1
index=3, key=2
index=4, key=6
index=5, key=8
index=6, key=7
index=7, key=4

Sorted:[1, 2, 5, 3, 6, 4, 7, 8]

Gap=1
index=1, key=2
index=2, key=5
index=3, key=3
index=4, key=6
index=5, key=4
index=6, key=7
index=7, key=8

Sorted:[1, 2, 3, 4, 5, 6, 7, 8]

Complexity Analysis: