A simple example of implementing the hill sorting algorithm using Java

Introduction to the
Hill sorting (narrow incremental method) as part of the insertion sort, put forward by Shell, hill sorting has carried on the simple improvement: to direct insertion sort it by enlarging the spacing between the elements of insertion sort, and in these elements with interval insertion sort, so that the data item to move, and large span when these data items after 1 visit to sequence, hill sorting algorithms reduce the interval of data items sorted again, so on, these sort of the gap between the data items are called incremental, traditionally h with letters to represent the increment.
The commonly used h sequence is proposed by Knuth, which starts from 1 and is generated by the following formula:

h = 3 * h +1

In turn, the program needs to reverse the calculation of the h sequence, which should be used

h=(h-1)/3

Code implementation
Implementation code 1:

public static void shellSort(int[] arr){
  int temp;
  for (int delta = arr.length/2; delta>=1; delta/=2){               // For each increment 1 Time sequence 
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ // Notice that the delta and the difference are everywhere delta
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

Implementation code 2:

public static void shellSort2(int[] arr){
  int delta = 1;
  while (delta < arr.length/3){//generate delta
    delta=delta*3+1;  // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
  }    
  int temp;
  for (; delta>=1; delta/=3){
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

The difference between direct insertion sort and direct insertion sort is that h in direct insertion sort is replaced by 1.
The Shell sort is unstable, and its space overhead is also O(1), and its time overhead is estimated to be between O(N 3/2) and O(N 7/6).