在合并排序递归中打印错误的索引值

Question

#include<iostream>
using namespace std;

void merge(int* arr, 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]=arr[l+i];
    for(int i=0; i<n2; i++)
        R[i]=arr[mid+1+i];
    int i=0,j=0,k=l;
    while(i<n1 && j<n2){
        if(L[i]<=R[j])
            arr[k++]=L[i++];
        else
            arr[k++]=R[j++];
    }
    while(i<n1)
        arr[k++]=L[i++];
    while(j<n2)
        arr[k++]=R[j++];
}

void mergesort(int* arr, int l, int r)
{
    if(l<r){
        int mid=(l+r)/2;
        printf("MS(%d, %d)\n", l,r);
        mergesort(arr, l, mid);
        printf("MS(%d, %d)\n", l,r);
        mergesort(arr, mid+1, r);
        printf("MS(%d, %d)\n", l,r);
        merge(arr, l, mid, r);
        printf("Afte Merge:    MS(%d, %d)\n", l,r);
    }
}

int main()
{
    int arr[] = {5, 2, 1, 6, 7, 9, 4};
    mergesort(arr, 0, 6);
    for(auto x:arr)
        cout<<x<<' ';

    return 0;

}

我正在打印 l 和 r 的值，以在每次递归调用时检查它们的值。但它不是很正确。第一次合并后的一个例子是：-

OUTPUT:
MS(0, 6)
MS(0, 3)
MS(0, 1)
MS(0, 1)
MS(0, 1)
Afte Merge:    MS(0, 1)

此处第 4 行和第 5 行（从 1 开始为 MS(0, 6)）应分别打印 MS(0,0) 和 MS(1,1)。请告诉我我做错了什么我想要正确的输出。
此致，

Answer 1

因为 l == r 所以无法打印 MS(0,0)。

如果你使用 if(l <= r) 就会死循环

所以，您的代码是准确的。

if(l<r){
        int mid= l + (r-l)/2;
        printf("MS(%d, %d)\n", l,r);
        mergesort(arr, l, mid);
        printf("MS(%d, %d)\n", l,r);
        mergesort(arr, mid+1, r);
        printf("MS(%d, %d)\n", l,r);
        merge(arr, l, mid, r);
        printf("Afte Merge:    MS(%d, %d)\n", l,r);
    }

在合并排序递归中打印错误的索引值

Printing wrong index values in mergesort recursion

c++

sorting

algorithm

mergesort

output