import java.util.Arrays;
public class ShellSort {
public static int[] arr = {3, 2, 4, 1, 6, 8, 0};
/* h = 4
* 3, 2, 4, 1, 6, 8, 0
* 3, 2, 4, 1, 6, 8, 0
* 3, 2, 0, 1, 6, 8, 4
* h = 1
* 2, 3, 0, 1, 6, 8, 4
* 0, 2, 3, 1, 6, 8, 4
* 0, 1, 2, 3, 6, 8, 4
* 0, 1, 2, 3, 6, 8, 4
* 0, 1, 2, 3, 6, 8, 4
* 0, 1, 2, 3, 4, 6, 8
*
* h=h*3+1
*
* 1, 4, 13, 40, 121...
*/
public static int[] sort(int[] a) {
int N = a.length;
int h = 1;
while(h < N) h = h*3+1;
while(h > 0) {
for(int i = h; i < N; i++) {
for(int j = i; j >=h && a[j] < a[j - h]; j -= h) {
int t = a[j];
a[j]=a[j-h];
a[j-h]=t;
}
}
h = h/3;
}
return a;
}
public static void main(String[] args) {
Arrays.stream(sort(arr)).forEach(System.out::println);
}
}
