递归归并排序代码输出重复元素问题排查求助

I spot the issue immediately—your merge function has a critical mistake in the final copy step that's overwriting parts of your array with uninitialized values, leading to unexpected duplicates. Let's break down what's happening and how to fix it:

The Root Cause #

In the merge function, after merging elements into the temporary array b, you're copying values back to the original array starting from index 0:

for (int i = 0; i <= h; i++)
    arr[i] = b[i];

But here's the problem: your temporary array b only contains valid merged values starting from index l (since you initialized k = l and filled b starting at that position). The elements from 0 to l-1 in b are uninitialized garbage. When you copy these into arr, you're overwriting the already sorted elements before l with random values, which often manifest as duplicates in your final output.

The Simple Fix #

Adjust the copy loop to start at l instead of 0, so you only copy the segment of b that you actually populated:

for (int i = l; i <= h; i++)
    arr[i] = b[i];

Corrected Full Code #

Here's the fixed version of your code, plus a note about a non-standard feature you might want to address for portability:

#include <iostream>
using namespace std;

void merge(int arr[], int l, int mid, int h) {
    int i = l;
    int j = mid + 1;
    int k = l;
    // Note: Variable-length arrays (VLAs) like int b[h+1] are not standard C++
    // For cross-compiler compatibility, use dynamic allocation or vector<int> instead
    int b[h + 1];
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            b[k++] = arr[i++];
        else
            b[k++] = arr[j++];
    }
    while (i <= mid)
        b[k++] = arr[i++];
    while (j <= h)
        b[k++] = arr[j++];
    // Corrected loop: only copy the valid merged segment
    for (int i = l; i <= h; i++)
        arr[i] = b[i];
}

void Rmerge_sort(int arr[], int l, int h) {
    if (l < h) {
        int mid = (h + l) / 2;
        Rmerge_sort(arr, l, mid);
        Rmerge_sort(arr, mid + 1, h);
        merge(arr, l, mid, h);
    }
}

int main() {
    int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 10}, n = 10;
    Rmerge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Bonus: Standard C++ Improvement #

The variable-length array int b[h+1] is a C99 feature that isn't part of standard C++. To make your code fully portable, replace it with a vector<int>:

#include <vector> // Add this include at the top

// Inside merge function:
vector<int> b(h + 1);

When you run the corrected code, it will output the properly sorted array without duplicates: 1 2 3 4 5 6 7 8 9 10.

内容的提问来源于stack exchange，提问作者Awasthi007