Verwendet diese Implementierung von merge sort gegenseitige Rekursion?

Question

Verwendet dieser mergeSort Algorithmus gegenseitige Rekursion? Ich realisiere, dass mergeSort ruft die merge Funktion und es nennt sich selbst (mergeSort), aber seit merge ruft nicht mergeSort ist es nicht gegenseitige Rekursion und einfach nur Rekursion?

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

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

Answer 1

Richtig: Dies ist eine einfache Rekursion. Gegenseitige Rekursion wird auch indirekte Rekursion genannt: A ruft B; B nennt A.

Ihre Analyse ist genau richtig: waren mergemergeSort, rufen dann Sie gegenseitige Rekursion haben würde. Im gebuchten Code ist der Anruf an merge ein einfacher Eltern-Kind-Link in der Anrufstruktur.

Answer 2

Um eine Erklärung über gegenseitige Rekursion für merge sort zu erhalten, ist dies eine der Methoden zur Optimierung der Sortierung von oben nach unten, um einen Kopierschritt während der Zusammenführung zu vermeiden, wobei die Richtung der Zusammenführung von der Ebene abhängt Rekursion. Die Alternative dazu ist, ein Flag als Parameter für die Zusammenführungsrichtung zu übergeben. Im folgenden Beispielcode ist a [] das ursprüngliche Array, b [] ist das funktionierende Array. TopDownSplitMergeAtoA kehrt mit sortierten Daten im ursprünglichen Array zurück und TopDownSplitMergeAtoB kehrt mit sortierten Daten im Arbeitsarray zurück, wobei TopDownSplitMergeAtoA TopDownSplitMergeAtoB aufruft und umgekehrt (dies ist die gegenseitige Rekursion). Der einzige Kopiervorgang findet statt, wenn die Größe des Unterarrays für TopDownSplitMergeAtoB eins ist. In diesem Fall wird ein Element vom ursprünglichen Array in das aktive Array kopiert.

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 
     } 
    } 
}