C ++使用动态数组时的合并排序问题

Question

我正在尝试实现合并排序功能，但合并部分有问题。由于最初我不知道数组大小，所以我创建了一个临时动态数组来存储最终的合并数组。当我运行这个方法时，我得到一个堆损坏错误。当我将动态数组大小更改为 (last + 1) 时，方法运行s 没有错误。我不知道为什么这会导致问题，因为最终数组中的元素数必须是 last - first + 1.

我的合并函数

void merge(int arr[], int first, int mid, int last) {
    int* temp = new int[last - first + 1];

    int first1 = first;
    int last1 = mid;
    int first2 = mid + 1;
    int last2 = last;
    int i = first1;

    while (first1 <= last1 && first2 <= last2) {
        if (arr[first1] < arr[first2]) {
            temp[i] = arr[first1];
            first1++;
        }
        else {
            temp[i] = arr[first2];
            first2++;
        }
        i++;
    }
    
    while (first1 <= last1) {
        temp[i] = arr[first1];
        first1++;
        i++;
    }

    while (first2 <= last2) {
        temp[i] = arr[first2];
        first2++;
        i++;
    }
    
    for (int k = first; k <= last; k++) {
        arr[k] = temp[k];
    }

    delete[] temp;
}

Answer 1

初始化用作 temp 到 first1 的索引的 i 是错误的，因为 temp 只有 [=16= 之间范围的元素] 和 last.

i 应初始化为零，循环

    for (int k = first; k <= last; k++) {
        arr[k] = temp[k];
    }

应该是

    for (int k = first; k <= last; k++) {
        arr[k] = temp[k - first];
    }

C ++使用动态数组时的合并排序问题

C++ merge sort problem while using dynamic array

c++

mergesort

dynamic-arrays