合并排序中的递归如何工作？内存将如何分配？

Question

堆栈内存将如何分配？
我无法理解递归如何在这里工作
请解释在分区函数中注释了“第4行”的行。并解释何时会执行此行？

void partition(int arr[],int low,int high){ 

     int mid; 

     if(low<high){ 
      mid=(low+high)/2; 
      partition(arr,low,mid); 
      partition(arr,mid+1,high); //line 4 
      mergeSort(arr,low,mid,high); 
     } 
    } 

    void mergeSort(int arr[],int low,int mid,int high){ 

     int i,m,k,l,temp[MAX]; 

     l=low; 
     i=low; 
     m=mid+1; 

     while((l<=mid)&&(m<=high)){ 

      if(arr[l]<=arr[m]){ 
       temp[i]=arr[l]; 
       l++; 
      } 
      else{ 
       temp[i]=arr[m]; 
       m++; 
      } 
      i++; 
     } 

     if(l>mid){ 
      for(k=m;k<=high;k++){ 
       temp[i]=arr[k]; 
       i++; 
      } 
     } 
     else{ 
      for(k=l;k<=mid;k++){ 
       temp[i]=arr[k]; 
       i++; 
      } 
     } 

     for(k=low;k<=high;k++){ 
      arr[k]=temp[k]; 
     } 

Answer 1

检查这幅画了其MergSort的图形表示

第一行是代表原始阿雷。 现在分区功能将被调用。第3行将在{38,27,43,3} 上调用分区功能，第4行将在{9,82,10}上调用分区函数，并将它们分成小分区，并且将再次调用相同的函数。 此过程将持续至最低<高。在图片中直到第4行。之后，它将回来，并将开始通过MargSort函数合并这些分区。