ShellSort

    public static void shell(int[] array) {
        int h = 1;
        while (h < array.length)
            h = h*3+1;
        // grouping
        while (h != 1) {
            h = (h-1)/3;
            // looping on each group.
            for (int start = 0; start < h; start++) {
                int count = array.length/h + (array.length%h == 0 ? 0 : 1);
                // the insertion
                for (int i = 1; i < count; i++) {
                    if (start+i*h >= array.length) break;
                    int t = array[start+i*h], j;
                    for (j = i-1; j >= 0 && array[start+j*h] > t; j--)
                        array[start+(j+1)*h] = array[start+j*h];
                    array[start+(j+1)*h] = t;
                }
            }
        }
    }