在 C++ 中合并排序意外输出

Question

这是我的归并排序代码，但是这段代码输出了错误的答案，我检查了好几次都没有找到输出错误的原因。如果有人能告诉我为什么会这样，我将不胜感激。

#include<bits/stdc++.h>
    using namespace std;
    void merge(int a[],int l,int m,int h){
        int n1=m-l+1;
        int n2=h-m;
        int L[n1],R[n2];
        int i,j,k;
        for( i=0;i<n1;i++){
            L[i]=a[l+i];
        }
        for(j=0;j<n2;j++){
            R[j]=a[m+1+j];
        }
        i=0;j=0;k=0;
        while(i<n1 && j<n2){
            if(L[i]<R[j]){
                a[k]=L[i];
                i++;
            }else{
                a[k]=R[j];
                j++;
            }

            k++;
        }
        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            k++;
            j++;
        }

    }
    void mergesort(int a[],int l,int h){
    if(l<h){
        int mid=l+(h-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,h);
        merge(a,l,mid,h);
    }}
    void printArray(int A[], int size) 
    { 
        int i; 
        for (i=0; i < size; i++) 
            printf("%d ", A[i]); 
        printf("\n"); 
    } 
    int main(){
       int n;
        scanf("%d",&n);
        int arr[n];
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        int arr_size = sizeof(arr)/sizeof(arr[0]); 

        printf("Given array is \n"); 
        printArray(arr, arr_size); 

        mergesort(arr, 0, arr_size - 1);
        printf("\nSorted array is \n"); 
        printArray(arr, arr_size); 
        return 0; 

    }

输入：

5

5 4 3 2 1

输出：

给定的数组是
5 4 3 2 1

排序数组为
1 2 1 2 5

Answer 1

您使用 merge 中的错误值初始化 k。

k=0; 会将指针保持在开头，而不是使用 k=l; 开始将值复制到当前合并段的左边界。

void merge(int a[],int l,int m,int h){
    int n1=m-l+1;
    int n2=h-m;
    int L[n1],R[n2];
    int i,j,k;
    for( i=0;i<n1;i++){
        L[i]=a[l+i];
    }
    for(j=0;j<n2;j++){
        R[j]=a[m+1+j];
    }
    i=0;j=0;k=l;
    while(i<n1 && j<n2){
        if(L[i]<R[j]){
            a[k]=L[i];
            i++;
        }else{
            a[k]=R[j];
            j++;
        }

        k++;
    }
    while(i<n1){
        a[k]=L[i];
        i++;
        k++;
    }
    while(j<n2){
        a[k]=R[j];
        k++;
        j++;
    }
}

在 C++ 中合并排序意外输出

Merge sort unexpected output in c++

c++

sorting

algorithm

mergesort