ALDS1_2_D Shell Sort

問題
シェルソート | アルゴリズムとデータ構造 | Aizu Online Judge

ALDSの問題を最初から解きなおしているのですが、この問題は解かずに放置していたので初めての取り組みです。
シェルソートとは挿入ソートを改良したものです。以下のページが分かり易かったです。
programming-place.net

間隔の決め方ですが、要素数nを2で割った商にしました。例えば、n=53なら 26,13,6,3,1　って感じです。
これでもacceptされたのですが、どうやらhn+1 = 3hn + 1（1,4,13,40,121…）を選ぶのが一番効率が良いそうです。
こっちも実装してみたのですが、実行時間にさほど差がありませんでした。

#include<stdio.h>
#define N 1000000

int a[N];
int cnt=0;
int G[N];
int m=1;

void insertionSort(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];
			cnt++;
			j=j-g;
		}
		a[j+g]=v;
	}
	return;
}


void shellSort(int n){
	int temp=n;
	
	G[0]=1;
	
	while(1){
		G[m]=G[m-1]*3+1;
		if(G[m] > n)break;
		m++;
	}
	
	for(int i=m-1;i>=0;i--)
		insertionSort(n,G[i]);
	
	return;
}



int main(){
	int n,i;
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	shellSort(n);
	
	
	printf("%d\n",m);
	for(i=m-1;i>0;i--)
		printf("%d ",G[i]);
	printf("%d\n",G[0]);
	
	printf("%d\n",cnt);
	
	for(i=0;i<n;i++)
		printf("%d\n",a[i]);
	
	return 0;
	
}

なんで1,4,13,40…が良いんでしょうね。