// ■非再帰マージソフト
//   通常のマージソフトは再帰的呼び出しで定義されるが、
//   再帰的呼び出しの部分を省略し、繰り返しで表現する方法。
//   
//      |□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|(1個毎の比較)
// 　   | ↓  | ↓  | ↓  | ↓  | ↓  | ↓  | ↓  | ↓  |
//      |□□ |□□ |□□ |□□ |□□ |□□ |□□ |□□ |(2個ずつマージ）
// 　　 |    ↓     |    ↓     |    ↓     |     ↓    | 
//      | □□□□  | □□□□  | □□□□  | □□□□  |(4個ずつマージ）
// 　　 |          ↓           |          ↓           |
//      |   □□□□□□□□    |   □□□□□□□□    |(8個ずつマージ）
// 　　 |　                    ↓                       |
//      |       □□□□□□□□□□□□□□□□        |(ソート完了）
//       
//   なおデータ数は 2^n個とは限らないので、データ数との比較を行い、
//   データ数を超える部分の処理を取りやめる判断を行う。
//
//      　    　 |               |               |
//      　    　 |    (2^n個)    |    (2^n個)    |
//      　    　 |               |               |
//     処理済み→+←-- 範囲1 --→+←-- 範囲2 --→+→次回の対象
//      　    　 |               |               |
//      　　　   |N0    i1       |N1      i2     |N2
//           　  |↓　　↓　　　 |↓      ↓     |↓
//      ■■■■■□□□□□□□□□□□□□□□□■■■■■
//
/
//     �@ マージ数=1，入力側 = 0，出力側 = 1とする。
//     �A マージ範囲 N0, N1, N2を設定。
//     �B 上記においてN0≦i1＜N1，N1≦i2＜N2として
//     　 tmp[k1][i1]とtmp[k1][i2]を比較して
//     　 小さい方をtmp[k2][j]に移す。なおN0≦j＜N2となる。
//     �C i2≧N2となったらi1側の残りを作業域側に移して次のマージへ。
//        i1≧N1となったらi2側の残りを作業域側に移して次のマージへ 。 
//     �D N0=N2として新しいマージ範囲を設定して�B以降を繰り返す。
//     �E N0がデータ数より大きくなったら
//        入力側と出力側を交換してマージ数を２倍にして�A以降を繰り返す。  
// 
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define DATALENGTH 10							//データ数
#define frand()((double)rand()/(RAND_MAX+1))	// 0〜1の間の乱数
int Data[DATALENGTH];							// ソート対象データ
void initArray(){// ソート対象データの生成(10 〜 99)
	for(int i=0;i<DATALENGTH;i++) Data[i]=(int)(frand()*89)+10;
}
int arrayMove(int A[2][DATALENGTH], int kin,int kout,int j, int ist, int ied){
	for(int i=ist;i<ied;i++) A[kout][j++]=A[kin][i];
	return j;
}
void loopMergeSort(){// 非再帰マージソフト
	int i, step,k1=0, k2=1, tmp[2][DATALENGTH];		// k1:マージ対象，K2:マージ結果
	for(i=0;i<DATALENGTH;i++)tmp[k1][i] = Data[i];	// ソート対象データを作業領域に移す
	for(step = 1; step < DATALENGTH; step *= 2){	// マージする数を 1, 2, 4, 8, …とする 
		int N2 = 0, j = 0;
		while(N2 < DATALENGTH){ //データ長だけ繰り返す
			int N0 = N2, N1 = N0 + step; // N1>=データ数であればN0〜N1までを複写してbreak
			if(N1 >= DATALENGTH){j = arrayMove(tmp, k1, k2, j, N0, DATALENGTH);break;}
			N2=N1+step; if(N2 > DATALENGTH) N2 = DATALENGTH;// N2>データ数のときN2=データ数
			int i1=N0, i2=N1;// i1=N0, i2=N1としてマージ開始
			while(i1<N1){// i1側とi2側の小さい方を出力する。
				if(i2>=N2){j = arrayMove(tmp, k1, k2, j, i1, N1);break;}//i1側を複写して次へ
				if(tmp[k1][i1]>tmp[k1][i2])	tmp[k2][j++]=tmp[k1][i2++];
				else						tmp[k2][j++]=tmp[k1][i1++];
			}
			j = arrayMove(tmp, k1,k2,j,i2,N2);//i2側を複写して次へ
		}
		k1 = k2; k2 = 1 - k2;//入出力の逆転
	}
	for(i=0;i<DATALENGTH;i++) Data[i]=tmp[k1][i];	// ソート結果を対象データに移す
}
int main(){
	srand((unsigned int)(time(NULL)));//乱数値の初期設定
	int i; initArray();
	printf(" ソート前： %d",Data[0]);
	for(i=1;i<DATALENGTH;i++) printf(", %d",Data[i]);
	printf("\n");
	loopMergeSort();
	printf(" ソート後： %d",Data[0]);
	for(i=1;i<DATALENGTH;i++) printf(", %d",Data[i]);
	loopMergeSort();
	printf("\n");
	getchar();
}