分治法MergerSort函数里的递归我实在是不清楚 大家帮我下 讲下过程。

#include <iostream>
#include <conio.h>
#include <malloc.h>

using namespace std;


const int array_size = 5;

void Merger(int A[], int p, int q, int r); // void Merger(int * A, int p, int q, int r);
void MergerSort(int A[], int p, int r); // void MergerSort(int * A, int p, int r);

// p为数组A第一个元素位置 r为数组A最后一个元素位置

int main()
{
    int A[array_size] = {0,4,2,3,1};
    int i = 0;
    MergerSort(A, 0, array_size-1);
    for (int i = 0; i < array_size; i++)
    {
        cout << A[i] << " ";
    }
   
    getch();
    return 0;
}

//p为数组A第一个元素位置 r为数组A最后一个元素位置
void MergerSort(int A[], int p, int r) // void MergerSort(int * A, int p, int r)  就是这里的

{
        int mid = 0;
        if (p < r)
        {
                mid = (r + p) / 2;
                MergerSort(A, p, mid);
                MergerSort(A, mid + 1, r);
                Merger(A, p, mid, r);
        }
}

// p为数组A第一个元素位置 r为数组A最后一个元素位置 q为数组A中间位置
void Merger(int A[], int p, int q, int r) // void Merger(int * A, int p, int q, int r)
{                              
    int n1 = q - p + 1;
    int n2 = r - q ;
    int i = 0, k = 0, j = 0;   
    int L[n1 + 1]; // int * L = (int *)malloc(sizeof(int) * n1 + 1);
    int R[n2 + 1]; // int * R = (int *)malloc(sizeof(int) * n2 + 1);
    for (i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    for (i = 0; i < n2; i++)
    {
        R[i] = A[q + i + 1];
    }
    i = j = 0;
   
    for (k = p; k <= r; k++)
    {
        if ((i < n1 && j == n2) || (i < n1 && j < n2 && L[i] < R[j]))
            A[k] = L[i++];
        else if ((i == n1 &&j < n2) || (i < n1 && j < n2 && L[i] >= R[j]))
            A[k] = R[j++];
    }
    // free(L);    // 清理L之前申请的内存
    // free(R);    // 清理L之前申请的内存
}