Shell Sort

 
    void shellSort(int[] arr){
        int N = arr.length;
        int h = 1;
        while(h < N/3) h = h * 3 + 1;
        while(h >= 1) {
            for(i = h; i < N; i++) {
                for(j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    int tmp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = arr[j];
                }
                h = h/3;
            }
        }
    }