#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "conio.h"
#define frand() ((double)rand()/(RAND_MAX+1))
#define NUM 22
static int data[2][NUM];
void setData(){
	for(int i=0;i<NUM;i++)data[0][i]=(int)(frand()*100);
}
void printDT(int k){
	for(int i=0;i<NUM;i++){
		if((i % 16)==0)printf("\n");
		printf("%4d", data[k][i]);
	}
}
int moveArray(int k1,int k2,int j, int i1,int i2){
	for (int i = i1; i < i2; i++) data[k2][j++] = data[k1][i];
	return j;
}
int impMergeSort(){
	int k1 = 0, k2=1;//最初の入力側を0，出力側を1とする
	for (int step = 1; step < NUM; step *= 2){
		int N2 = 0; int j = 0;
		while (N2 < NUM){// step幅のマージ(初期値はstep=1)
			int N0 = N2, N1 = N0 + step;
			if (N1 >= NUM) { j = moveArray(k1,k2, j, N0, NUM); break; }
			N2 = N1 + step; if (N2 > NUM) N2 =NUM;
			int i1 = N0; int i2 = N1;
			while (i1 < N1){// マージ処理
				if (i2 >= N2) { j = moveArray(k1,k2, j, i1, N1); break; }
				if (data[k1][i1] > data[k1][i2]) data[k2][j++] = data[k1][i2++];
				else                             data[k2][j++] = data[k1][i1++];
			}
			j = moveArray(k1, k2, j, i2, N2);//後半部の残りを複写
		}
		k2 = k1; k1 = 1 - k1;// 入力側と出力側を切り替え
	}
	return k1;//ソート結果が入っている添字を返す
 
}
void initRand(){
	srand((int)time(NULL));rand();
}
int main(){
	int K;initRand();
	do{
		printf("\n\nソート前"); setData()       ;printDT(0);
		printf("\n\nソート後"); K=impMergeSort();printDT(K);
		printf("\n\n終わる時は[ctrl]+'Z'\n");
	}
	while(getch()!=0x1A);
	return 0;
}