二重集計ソートの再帰的な書き方と反復的な書き方

1.問題の説明:
与えられたシーケンスに対して二重集計ソートアルゴリズムを用いてソートする
2.構想分析:
①2ウェイ集計ソートは、シーケンスを2つの半分に分割し、半分ごとにソートしてから統合するプロセスと見なすことができ、分割された一般的には同じ方法でソートすることができ、その後、秩序あるシーケンスが得られ、上記の説明から問題の規模が徐々に小さくなっていることがわかります.しかも同じ方法で解決しているので、第1の方法は再帰的に解決することができます.
②再帰的な方法を用いて解くと、まず序列を二つに分け、二つに分けた序列を並べ替え、左右に並べた序列を統合する必要があるので、核心的な方法は二つの順序の序列を一つの順序の序列に統合する方法を書くことである
③連結シーケンスの方法では、いくつかのパラメータを入力する必要があり、左半分の整列部分の開始端点と終了端点、さらに右半分の整列部分の開始端点と終了端点を入力する必要があります.2つのポインタが左半分の区間の開始端点と右半分の開始端点をそれぞれ指していることを定義する必要があります.ifを使用して、どの要素が小さいかを判断します.ここでは、中間要素を格納するために追加の配列を使用する必要があります.統合されたすべての数字を1つの補助配列に格納します.ループの実行条件は、左区間と右区間がまだ区間の果てに達していないため、1つの区間が終わりになっている場合があります.もう一つの区間に要素がある場合は、残りの要素をこの補助配列に加えると判断し、最後に補助配列の要素をすべて前の配列に割り当てる必要があります.
④上記の再帰的解法に加えて反復的解法を用いて解くことも可能であるが、実際には上記の再帰的解法の考え方から、毎回シーケンスに分けて2つの部分に分かれていることが分かるので、最初からステップ長stepを2に等しくし、配列中のstep個の要素を1組として内部をソートすることができる.左のstep/2を右のstep/2要素とマージし、step/2に2を乗じて上の操作を繰り返します.step/2が要素の個数nを超えるまで、反復的な方法で行うと理解しにくいと思います.具体的な例に基づいてプログラムの下付きの位置を特定する必要があります.
3.具体的なプログラムコードは次のとおりです.
①再帰的実現:

#include
const int maxn = 100;
void merge(int A[], int L1, int R1, int L2, int R2){
	int i = L1, j = L2;
	int temp[maxn], index = 0;
	while(i <= R1 && j <= R2){
		if(A[i] <= A[j]){
			temp[index++] = A[i++];
		}else{
			temp[index++] = A[j++];
		}
	}
	while(i <= R1) temp[index++] = A[i++];
	while(j <= R2) temp[index++] = A[j++];
	for(int i = 0; i < index; ++i){
		A[L1 + i] = temp[i];
	} 
}
// array     [left, right]      
void mergeSort(int A[], int left, int right){
	if(left < right){
		int mid = (left + right) / 2;
		mergeSort(A, left, mid);
		mergeSort(A, mid + 1, right);
		merge(A, left, mid, mid + 1, right);
	}
} 

int main(void){
	int arr[9] = {12, 56, 2, 88, -7, 3, -1, 7, 100};
	mergeSort(arr, 0, 9 );
	for(int i = 0; i < 9; ++i){
		printf("%d ", arr[i]);
	}
	return 0;
}

②反復的に実装され、配列要素は以下の0から始まる.

#include
#include
#include
using namespace std;
const int maxn = 100;
const int n = 9;
void merge(int A[], int L1, int R1, int L2, int R2){
	int i = L1, j = L2;
	int temp[maxn], index = 0;
	while(i <= R1 && j <= R2){
		if(A[i] <= A[j]){
			temp[index++] = A[i++];
		}else{
			temp[index++] = A[j++];
		}
	}
	while(i <= R1) temp[index++] = A[i++];
	while(j <= R2) temp[index++] = A[j++];
	for(int i = 0; i < index; ++i){
		A[L1 + i] = temp[i];
	} 
}


void mergeSort(int A[]){
	//       0    
	for(int step = 2; step / 2 <= n; step *= 2){
		for(int i = 0; i < n; i += step){
			//step / 2              
			int mid = i + step / 2 - 1;
			if(mid + 1 < n){
				merge(A, i, mid, mid + 1, min(i + step - 1, n - 1));
			}
		}
	}
}

int main(void){
	int arr[9] = {12, 56, 2, 88, -7, 3, -1, 7, 100};
	mergeSort(arr);
	for(int i = 0; i < 9; ++i){
		cout << arr[i] << " ";
	}
	return 0;
}

③反復的に実装され、配列要素は以下の1から始まる.

#include
#include
#include
using namespace std;
const int maxn = 100;
const int n = 9;
void merge(int A[], int L1, int R1, int L2, int R2){
	int i = L1, j = L2;
	int temp[maxn], index = 0;
	while(i <= R1 && j <= R2){
		if(A[i] <= A[j]){
			temp[index++] = A[i++];
		}else{
			temp[index++] = A[j++];
		}
	}
	while(i <= R1) temp[index++] = A[i++];
	while(j <= R2) temp[index++] = A[j++];
	for(int i = 0; i < index; ++i){
		A[L1 + i] = temp[i];
	} 
}

void mergeSort(int A[]){
	for(int step = 2; step / 2 <= n; step *= 2){
		for(int i = 1; i <= n; i += step){
			int mid = i + step / 2 - 1;
			if(mid + 1 <= n){
				//  min         step             
				merge(A, i, mid, mid + 1, min(i + step - 1, n));
			}
		}
	}
}

int main(void){
	int arr[10] = {0, 12, 56, 2, 88, -7, 3, -1, 7, 100};
	mergeSort(arr);
	for(int i = 1; i <= 9; ++i){
		cout << arr[i] << " ";
	}
	return 0;
}