C++归并排序报错:terminate called after throwing an instance of 'std::bad_array_new_length',求解


#include <iostream>

void merge(int arr[], const int l, const int r, const int m);
void merge_sort(int arr[], const int l, const int r);

int main()
{
    int arr[8] = {2, 4, 1, 0, 7, 9, 5, 3};
    merge_sort(arr, 0, 7);
    for (int i = 0; i < 8; i++)
    {
        std::cout << arr[i] << '\n';
    }
    return 0;
}

void merge(int arr[], const int l, const int r, const int m)
{
    int *left = new int[m - l];
    int *right = new int[r - m + 1];
    int i, j, k;

    for (i = l; i < m; i++)
    {
        left[i - l] = arr[i];
    }

    for (i = m; i <= r; i++)
    {
        right[i - m] = arr[i];
    }

    i = j = 0;
    k = l;

    while (i < (m - l) && j < (r - m + 1))
    {
        if (left[i] < right[j])
        {
            arr[k] = left[i];
            i++;
            k++;
        }
        else
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    while (i < (m - l))
    {
        arr[k] = left[i];
        i++;
        k++;
    }

    while (j < (r - m + 1))
    {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int l, int r)
{
    int m = (l + r) / 2;
    if (l < r)
    {
        int m = (l + r) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

逻辑有问题,左序数组的大小应该是m-l+1,右序数组的大小是r-m,代码修改如下:


#include <iostream>
void merge(int arr[], const int l, const int r, const int m);
void merge_sort(int arr[], const int l, const int r);
int main()
{
    int arr[8] = {2, 4, 1, 0, 7, 9, 5, 3};
    merge_sort(arr, 0, 7);
    for (int i = 0; i < 8; i++)
    {
        std::cout << arr[i] << '\n';
    }
    return 0;
}
void merge(int arr[], const int l, const int r, const int m)
{
    int *left = new int[m - l+1];
    int *right = new int[r - m ];
    int i, j, k;
    for (i = l; i <= m; i++)
    {
        left[i - l] = arr[i];
    }
    for (i = m+1; i <= r; i++)
    {
        right[i - m-1] = arr[i];
    }
    i = j = 0;
    k = l;
    while (i <= (m - l) && j < (r - m ))
    {
        if (left[i] < right[j])
        {
            arr[k] = left[i];
            i++;
            k++;
        }
        else
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    while (i <= (m - l))
    {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < (r - m ))
    {
        arr[k] = right[j];
        j++;
        k++;
    }
    delete[] left;
    delete[] right;
}
void merge_sort(int arr[], int l, int r)
{
    //int m = (l + r) / 2;
    if (l < r)
    {
        int m = (l + r) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
        merge(arr, l, r, m);//merge(arr, l, m, r);
    }
}