このマージソートの実装は相互再帰を使用しますか？

Question

このmergeSortアルゴリズムは相互再帰を使用しますか？私はmergeSortがmerge関数を呼び出し、それ自身（mergeSort）を呼び出しますが、mergeはmergeSortを呼び出さないので、それは相互再帰ではなく、単に再帰であるのですか？

function mergeSort(arr) { 
    // split array 
    ... 
    return merge(mergSort(firstHalf), mergeSort(secondHalf)); 
} 

function merge (array1, array2) { 
    // merge both arrays 
    ... 
    return singleArray; 
} 

Answer 1

正しい：これは単純な再帰です。相互再帰は、間接再帰とも呼ばれます。 Bは、あなたの分析A.

を呼び出して、正確に正しいです：あなたは相互再帰を持っているでしょうそしてmergeSort、を呼び出すためにmergeました。投稿されたコードでは、mergeへの呼び出しは、呼び出しツリー上の単純な親子リンクです。

Answer 2

マージソートの相互再帰について説明すると、マージ中のコピーステップを避けるためにトップダウンマージソートを最適化する方法の1つで、マージの方向はレベル再帰。これに代わる方法は、マージする方向のパラメータとしてフラグを渡すことです。下のサンプルコードでは、[]は元の配列、b []は作業配列です。 TopDownSplitMergeAtoAはソートされたデータを元の配列に返し、TopDownSplitMergeAtoBは、TopDownSplitMergeAtoBを呼び出してTopDownSplitMergeAtoBを呼び出す（これは相互再帰です）ソートされたデータを作業配列に返します。コピー操作は、サブ配列のサイズがTopDownSplitMergeAtoBの場合にのみ発生します。この場合、1つの要素が元の配列から作業配列にコピーされます。

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee); 

void MergeSort(int a[], size_t n)  // entry function 
{ 
    if(n < 2)       // if size < 2 return 
     return; 
    int *b = new int[n]; 
    TopDownSplitMergeAtoA(a, b, 0, n); 
    delete[] b; 
} 

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    Merge(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    Merge(a, b, ll, rr, ee);  // merge a to b 
} 

void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;      // b[]  index 
    size_t l = ll;      // a[] left index 
    size_t r = rr;      // a[] right index 
    while(1){       // merge data 
     if(a[l] <= a[r]){    // if a[l] <= a[r] 
      b[o++] = a[l++];   // copy a[l] 
      if(l < rr)     // if not end of left run 
       continue;    //  continue (back to while) 
      while(r < ee)    // else copy rest of right run 
       b[o++] = a[r++]; 
      break;      //  and return 
     } else {      // else a[l] > a[r] 
      b[o++] = a[r++];   // copy a[r] 
      if(r < ee)     // if not end of right run 
       continue;    //  continue (back to while) 
      while(l < rr)    // else copy rest of left run 
       b[o++] = a[l++]; 
      break;      //  and return 
     } 
    } 
}