请在此合并排序代码中发现错误

Question

我提供了使用合并排序算法对数组进行排序的代码，我找不到错误，此代码未提供输出正确排序的数组。 mergesort函数被递归调用以分割数组，直到其大小减小到1。然后使用merge函数合并多个数组。

#include <bits/stdc++.h>

using namespace std;

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

void mergesort(int a[], int l, int h) {
    if (l < h) {
        int m = l + (h - l) / 2;
        mergesort(a, l, m);
        mergesort(a, m + 1, h);
        merge(a, m, l, h);
    }
}

int main() {
    int a[5] = { 1, 2, 3, 4, 5 };
    mergesort(a, 0, 4);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

Answer 1

merge函数中的错误是r，应初始化为l，而不是0。您没有将切片合并到原始位置。

还请注意，此函数中的最后一个循环while (p < n2)是多余的：右切片中的其余元素已经在原始数组中的适当位置。

这里是修改后的版本：

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