c++ マージソートについて

Question

マージソートについてですが, void margeの中の上から3行目のL[i]を出力してみたところ,
入力がn=8,A[i]=8 7 6 5 4 3 2 1にすると, L[i]は8 6 7 8 4 2 3 4 5 6 7 8でした.

A[i]=8 7 6 5 4 3 2 1をマージソートすると,
8 7 6 5 4 3 2 1
7 8 5 6 3 4 1 2
5 6 7 8 1 2 3 4
1 2 3 4 5 6 7 8
となると思ったのですが,このL[i]は何を表しているのですか？

また最後は1234ではなく5678がL[i]に格納されている(?)のはなぜですか.

基本的な質問かもしれませんがよろしくお願いします.

#include<iostream>
using namespace std;

#define INFTY 2000000000
#define MAX 500000

int L[250000+2],R[250000+2];
int t=0;

void marge(int A[],int left,int mid,int right){
    int n1 = mid - left;
    int n2 = right - mid;

    for(int i=0;i<n1;i++) L[i] = A[left + i];　//ここです！
    for(int i=0;i<n2;i++) R[i] = A[mid + i];

    L[n1]=R[n2]=INFTY;

    int i=0,j=0;
    for(int k=left;k<right;k++)
    {
        t=t+1;
       if(L[i]<R[j]){
           A[k] = L[i];
           i = i+1;
       }else{
           A[k] = R[j];
           j = j+1;
       }
    }

}

void margeSort(int A[],int left,int right){
    if(left+1 < right){
        int mid = (left+right)/2;
        margeSort(A,left,mid);
        margeSort(A,mid,right);
        marge(A,left,mid,right);
    }
}

int main(){
    int A[MAX],n;

    cin >> n;
    for(int i=0;i<n;i++) cin >> A[i];

    margeSort(A,0,n);

    for(int i=0;i<n;i++){
        if(i)cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << t << endl;

    return 0;
}

Answer 1

void print(int L[], int n1, int R[], int n2)
{
	cout << "L:[ " << L[0];
	for (int i = 1; i < n1; i++) cout << ' ' << L[i];
	cout << " ]\t\tR:[ " << R[0];
	for (int i = 1; i < n2; i++) cout << ' ' << R[i];
	cout << " ]\n";
}

    for(int i=0;i<n1;i++) L[i] = A[left + i];//ここです！
    for(int i=0;i<n2;i++) R[i] = A[mid + i];
	print(L, n1, R, n2);

このようにすると、実行結果は次のようになりました。

8
8 7 6 5 4 3 2 1
L:[ 8 ]         R:[ 7 ]
L:[ 6 ]         R:[ 5 ]
L:[ 7 8 ]               R:[ 5 6 ]
L:[ 4 ]         R:[ 3 ]
L:[ 2 ]         R:[ 1 ]
L:[ 3 4 ]               R:[ 1 2 ]
L:[ 5 6 7 8 ]           R:[ 1 2 3 4 ]
1 2 3 4 5 6 7 8
24

merge sort では、入力の [8 7 6 5 4 3 2 1] を
[8 7 6 5] と [4 3 2 1] に分けます。

次に [8 7 6 5] を [8 7] と [6 5] に分けます。

次に [8 7] を [8] と [7] に分けます。
これが最初の　L:[ 8 ]　　　R:[ 7 ]　です。
これはマージされて [7 8] になりますが、デバッグ表示はまだ先です。

次に [6 5] を [6] と [5] に分けます。
これが2番目の　L:[ 6 ]　　　R:[ 5 ]　です。
これはマージされて [6 5] になります。
そして、3番目の　L:[ 7 8 ]　　　R:[ 5 6 ]　になります。
マージされて [5 6 7 8] になりますが、デバッグ表示は最後になります。

以下同様に [4 3 2 1] についてソートします。

最後は、L:[ 5 6 7 8 ]　　　R:[ 1 2 3 4 ]　をマージします。

Comments

[_._._ami]

非常にわかりやすく, 丁寧にありがとうございます...！！とても助かりました