C语言 : Why my code get infinite loop and how to use recursion to solve Merge Sort problem?

Question

我在这段代码中遇到了两个问题。

第一个问题是死循环，发生在77~79之间。当我更改此测试数据并改为使用 merge 方法时，我将陷入无限循环并且 R1 将更改为 4198739。但是如果我使用 mergeSort 方法，问题将不会按预期出现。如下图所示:

  int M = 2;
  int R1 = 4;
  int arr[] = {3,9,8,20};
  merge(arr, L, M, R1);

第二个问题发生在第 57 到 69 行。在这个 mergeSort 方法中，我试图将无序数组划分为子数组。但是对原数组没有任何影响。

这是我的代码。 Merge Sort in C

void mergeSort(int arr[], int L, int R)
{
  if(L<R) { 
    return ;
  } else {
    int M = (L+R) / 2;
    mergeSort(arr, L, M);
    mergeSort(arr, M+1, R);
    merge(arr, L, M+1 ,R);
  }
}

Answer 1

代码逻辑上有几个错误。我将解决它正确的代码。 先说几点。

1. 逻辑处理数组索引，不要与数组限制混淆。
2. 我已经使用 sizeof 运算符来获取数组的上限。
3. 尽可能使用 if-else。

这里无法正确添加完整代码，因此 - https://pastebin.com/ixickcQA

主要错误在这里:

for(i=M;i<=R;i++)               //1. <= as R is also an index
{
     right[i-M] = arr[i];
}