ALDS1_2_D: Shell Sort - sinapusu2002 @ ウィキ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D
昔の自分って頭良かったんだな。
Ｇが３倍+1で増えて1093まででいい理由がよくわからない。

#include<stdio.h>
 
int cnt;
int m;
int G[7]={1,4,13,40,121,364,1093};

int A[1000001];
void insertionSort(int *A,int n,int g){
   for(int i=g;i<n;i++){
       int v=A[i];
       int j=i-g;
       while(j>=0&&A[j]>v){
           A[j+g]=A[j];
           j-=g;
           cnt++;
       }
       A[j+g]=v;
   } 
}
 
void shellSort(int *A,int n){
   cnt=0;
   m=1+(G[1]<n)+(G[2]<n)+(G[3]<n)+(G[4]<n)+(G[5]<n)+(G[6]<n);
   for(int i=m-1;i>=0;i--){
       insertionSort(A,n,G[i]);
   }
}
 
int main(){
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++)scanf("%d",&A[i]);
   shellSort(A,n);
   printf("%d\n",m);
   for(int i=m-1;i>=0;i--)printf("%d%s",G[i],i>0?" ":"\n");
   printf("%d\n",cnt);

   for(int i=0;i<n;i++){
       printf("%d\n",A[i]);
   }
}