#include <stdio.h>
#include <malloc.h>

void d(int *a, int j, int r)
{
	while (j < r)
		printf("%d ", a[j++]);
	printf("\n");
}
 
void mergesort(int *a,int l,int r,int m) {
	if(l==r) return;
	printf("merge l=%d r=%d m=%d\n", l, r, m);
	mergesort(a,l,m,(l+m)/2);
	mergesort(a,m+1,r,(m+r+1)/2);
	int i=l,j=m+1,k, x=j;
	printf("> "); d(a, 0, 10);
	while(j!=r+1) {
		if(a[j]<=a[i]) {
			int tmp=a[j];
			for(k=j;k>i;k--)
				a[k]=a[k-1];
			a[i]=tmp;
			j++;
		}
		i++;
	}
	printf("< "); d(a, 0, 10);
}

int main() { 
	FILE *in = fopen("sort.in","r");
	FILE *out = fopen("sort.out","w");
	int N,i;
	fscanf(in,"%d\n",&N);
	int *array=malloc(N*sizeof(int));
	for(i=0;i<N;i++)
		fscanf(in,"%d ", array+i);
	mergesort(array,0,N-1,N/2);
	for(i=0;i<N;i++)
		fprintf(out,"%d ", array[i]);
	d(array, 0, N);
	free(array);
	fclose(out);
	fclose(in);	
	return 0;
}