这个合并排序的实现是否使用相互递归？

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

正确：这是简单的递归。相互递归也叫间接递归：A调用B； B 呼叫 A.

您的分析完全正确：如果merge调用mergeSort，然后您将进行相互递归。在发布的代码中，对 merge 的调用是调用树上的简单父子 link。

Answer 2

接着解释合并排序的相互递归，它是用于优化自上而下合并排序的方法之一，以避免合并过程中的复制步骤，其中合并的方向取决于级别的递归。另一种方法是传递一个标志作为合并方向的参数。在下面的示例代码中，a[] 是原始数组，b[] 是工作数组。 TopDownSplitMergeAtoA returns 在原始数组中使用排序数据，TopDownSplitMergeAtoB returns 在工作数组中使用排序数据，TopDownSplitMergeAtoA 调用 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
        }
    }
}

这个合并排序的实现是否使用相互递归？

Does this implementation of merge sort use mutual recursion?

javascript

sorting

recursion

mergesort

mutual-recursion