Merge_sort without sentinel

Question

有人可以告诉我为什么我在排序后得到垃圾值吗？ 最初的调用是(A,0,n)其中n是数组的大小？我想使用合并排序算法对数组进行排序，但没有定位值。

void merge_sort(int A[], int l, int mid, int r) 
{ 
    int n1 = mid - l + 1; 
    int n2 = r - mid; 

    int L[n1], R[n2]; 

    for (int i = 0; i < n1; i++) 
    { 
     L[i] = A[i]; 
    } 

    for (int i = 0; i <= n2; i++) 
    { 
     R[i] = A[i + mid + 1]; 
    } 
    cout << endl; 

    int j = 0, k = 0; 

    for (int i = l; i < r; i++) 
    { 
     if (j == n1 || k == n2) 
     { 
      if (j == n1 + 1) 
      { 
       A[i] = R[k]; 
       k++; 
      } 
      else 
      { 
       A[i] = L[j]; 
       j++; 
      } 
     } 
     else if (L[j] >= R[k]) 
     { 
      A[i] = L[j]; 
      j++; 
     } 
     else 
     { 
      A[i] = R[k]; 
      k++; 
     } 
    } 
} 

void merge_divide(int A[], int l, int r) 
{ 
    if (l < r) 
    { 
     int mid = (l + r)/2; 
     merge_divide(A, l, mid); 
     merge_divide(A, mid + 1, r); 
     merge_sort(A, l, mid, r); 
    } 
} 

Answer 1

你的逻辑中有很多动作难以阅读。很难区分哪里出错或者有什么意图。但这里是我如何看待修复。请参阅行内评论。

void merge_sort(int A[], int l, int mid, int r) { 
    int n1 = mid - l; 
    int n2 = r - mid; 

    // this is C, but not C++, consider using vector instead 
    int L[n1], R[n2]; 

    for (int i = 0; i < n1; i++) { 
    // need `l` here 
    L[i] = A[l + i]; 
    } 

    for (int i = 0; i < n2; i++) { 
    // need to include `mid` 
    R[i] = A[i + mid]; 
    } 

    int j = 0, k = 0; 

    for (int i = l; i < r; i++) { 
    if (j == n1) { 
     A[i] = R[k]; 
     k++; 
    } else if (k == n2) { 
     A[i] = L[j]; 
     j++; 
    } else if (L[j] >= R[k]) { 
     A[i] = L[j]; 
     j++; 
    } else { 
     A[i] = R[k]; 
     k++; 
    } 
    } 
} 

void merge_divide(int A[], int l, int r) { 
    // need properly compute `mid` here 
    int mid = r - l; 
    if (mid > 1) { 
    mid = l + mid/2; 
    merge_divide(A, l, mid); 
    merge_divide(A, mid, r); 
    merge_sort(A, l, mid, r); 
    } 
} 

int main() { 
    int A[] = {2, 4, 3, 382, 2342334, 3, 42, 234}; 
    int n = sizeof(A)/sizeof(int); 
    merge_divide(A, 0, n); 
    for (int i = 0; i < n; ++i) 
    cerr << A[i] << " "; 
    cout << endl; 
}