#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 10

//#define RAND	//もし自分で入力したいならコメントアウトしてね！

int merge(int *sort,int size);
int m_sort(int *a,int asize,int *b,int bsize);

int main(void)
{
	int sort[MAX];
	int i,size;

//ここから
#ifdef RAND
	srand((unsigned)time(NULL));

	size = MAX;

	for(i = 0; i < size; i++)
		sort[i] = rand() % 100;

#else
	for(i = 0; i < MAX; i++){
		scanf("%d",&sort[i]);
		if(sort[i] == EOF)
			break;
	}
	size = i;
	printf("%d\n",size);
#endif
//ここまでデータ入力

	merge(sort,size);	//いけっマージたん！出番だ！

	for(i = 0; i < size;i++)
		printf("%d\n",sort[i]);	//出力ーっ

	printf("何か文字を入力して終了\n");
	getch();
	return 0;
}

/*****************************
*         mergeたん          *
*   敵のHPを１まで減らして   *
*  １まで減らしたら、順番に  *
* m_sort関数で並び替えていく *
******************************/
int merge(int *sort,int size)
{
	int asize,bsize;

	asize = size/2;	
	bsize = size-asize;

	if(size > 1){
		merge(sort,asize);	//頑張れっ敵のHPは後少しだ！
		merge(&sort[asize],bsize);

		m_sort(sort,asize,&sort[asize],bsize);
	}
	return 0;
}

/*****************************
*      マージソートたん      *
*  ソートたんから受け取った  *
*                            *
*          ・・・・          *
*                            *
*もう思いつかないよおぉぉぉぉ*
*****************************/
int m_sort(int *a,int asize,int *b, int bsize)
{
	int ap,bp,i;
	int buf[MAX];

	ap = bp = i = 0;
	
	while(1){
		if(ap >= asize && bp >= bsize)	//配列を全て並べ替えたらbreak
			break;
		if(ap >= asize){	//aの配列が終わったら残りは全部bに入れる
			buf[i++] = b[bp++];
			continue;
		}
		if(bp >= bsize){	//bの配列が終わったら残りは全部aに入れる
			buf[i++] = a[ap++];
			continue;
		}

		if(a[ap] > b[bp])	//aとbを比べて小さいほうを入れる。
			buf[i++] = b[bp++];
		else
			buf[i++] = a[ap++];
	}


	for(i = 0; i < asize + bsize; i++)	//bufに蓄えたデータを配列に戻す。
		a[i] = buf[i];

	return 0;
}