for (increment=N/2; increment>0; increment/=2) {
    for (i=increment; i<N; i++) {
        tmp = A[i];
        for (j=i; j>=increment; j-=increment) {
            if (tmp < A[j-increment]) {
                A[j] = A[j-increment];
            }
            else
                break;
        }
        A[j] = tmp;
    }
}