/*
 Shell排序的主要思想是：将记录分为若干子序列，
 然后在各个子序列中进行插入排序，经过若干次
 操作便可以得到有序序列
 时间复杂度nlogn
*/

#include<cstdio>
#define MAX 1000

typedef struct SeqList
{
	int Array[MAX];
	int length;
}SeqList;

void ShellSort(SeqList *L)
{
	int i,j;
	int increment=L->length;
	do
	{
		increment=increment/3+1;
		for(i=increment+1;i<=L->length;i++)
		{
			if(L->Array[i]<L->Array[i-increment])
			{
				L->Array[0]=L->Array[i];//哨兵节点，临时存储数据
				for(j=i-increment;j>0&&L->Array[j]>L->Array[0];j-=increment)
				{
					L->Array[j+increment]=L->Array[j];
				}
				L->Array[j+increment]=L->Array[0];
			}
		}
	}while(increment>1);

}

int main(int argc,char *argv[])
{
	SeqList L;
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&L.Array[i]);
	L.length=n;
	ShellSort(&L);
	printf("After Sort:\n");
	for(i=1;i<=L.length;i++)
		printf("%4d",L.Array[i]);
 	printf("\n");

	return 0;
}