MergeSort 中的两个递归调用是什么？

Question

正在学习算法，但在理解 MergeSort 中两个递归调用的具体构成时遇到了一些困难。感谢帮助。谢谢。

Answer 1

设数组大小为N。基本上把数组分成两部分，形成 1 到 N/2 和 N/2 + 1 到 N。让我们分别称这些部分为 L 和 R。现在如果我们可以排序 L 和 R 分开我们可以将它们合并以获得最终结果。现在你如何排序 L 和 R ，再次应用相同的程序。因此有两个递归部分，一个递归排序 L 和 oe 两个递归排序 R 之后它们被合并。伪代码

      merge_sort ( 1 , N )
         merge_sort(1,N/2) /* L */
         merger_sort(N/2 + 1,N) /* R */
         merge both these sorted parts

Answer 2

你只用一个功能就可以达到同样的效果。这是伪代码：

def mergesort(int l, int r) {

  if l == r:
    return

  int mid = (l + r) / 2
  mergesort(l, mid)
  mergesort(mid + 1, r)

  merge left subarray and right subarray
}

这是 C++ 代码：

#include <cstdio>
#include <cstdlib>

using namespace std;
const int N = 1000003;

int tmp[N];
int a[N];

void merge_sort(int b, int e) {

  if(b == e) // if there is only one element, then we have an sorted subarray
    return;

  int mid = (b + e) / 2;
  merge_sort(b, mid); //recursive call
  merge_sort(mid + 1, e); //recursive call

  int sz = e - b + 1; // the size of the subarray

  for(int k = 0, i = b, j = mid + 1; k < sz; ++k) {

    if(i > mid) //if we have passed the border of left subarray, use the right one
      tmp[k] = a[j++];
    else if(j > e) // if we have passed the border of right subarray, use the left one
      tmp[k] = a[i++];
    else { // if all borders are oke
      if(a[i] > a[j]) // compare values in left and right subarray
        tmp[k] = a[j++];
      else
        tmp[k] = a[i++];
    }
  }  

  // sorted values form b to e are in tmp array, now just copy the tmp array to array a
  for(int i = 0, j = b; i < sz; ++i, ++j)
    a[j] = tmp[i]; 

}

int main() {

  int n; scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", &a[i]);

  merge_sort(0, n - 1);

  for(int i = 0; i < n; ++i)
    printf("%d ", a[i]);

  return 0;
}

MergeSort 中的两个递归调用是什么？

What are the two recursive calls in MergeSort?

algorithm

performance

mergesort