c++ - 合并排序处于无限循环中

Question

我正在尝试编写递归合并排序。
但是，当我运行代码时，我发现代码没有通过正确的数组。
请帮我解决问题。

void merge_sort_recursive(int *arr, int left, int right) {
    int mid;
    while (left < right) { 
        mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
    for (int i = 0; i < 4; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right + 1]; 
    int lPtr = left; 
    int rPtr = mid + 1;
    int bPtr = left; 

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] < arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }

    if (lPtr > mid) 
        for (int i = rPtr; i <= right; i++)
            buffer[bPtr++] = arr[i];
    else 
        for (int i = lPtr; i <= mid; i++)
            buffer[bPtr++] = arr[i];

    for (int i = left; i <= right; i++) 
        arr[i] = buffer[i]; 
}

Answer 1

您的代码中存在多个问题:

在merge_sort_recursive函数中的

中，您不应循环while (left < right)，而应递归地进行if (left < right)。

您应该删除merge_sort_recursive中的输出。我想您仅将其用于调试目的。

在函数 merge_recursive中的

中，您将分配一个大小为right + 1的临时数组。这太大了，right - left + 1就足够了(对索引值进行了调整)。

您不delete临时数组，导致大量内存泄漏

第一个合并循环中的测试应使用<=而不是<和

主要问题是 while循环，该循环阻止从递归调用中返回。

这是修改后的版本:

void merge_sort_recursive(int *arr, int left, int right) {
    if (left < right) { 
        int mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right - left + 1];
    int lPtr = left;
    int rPtr = mid + 1;
    int bPtr = 0;

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] <= arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }
    /* copy the remaining elements from the left part */
    while (lPtr <= mid) {
        buffer[bPtr++] = arr[lPtr++];
    }
    /* no need to copy the remaining elements from the right part 
       because they already are at the final position */
    for (int i = 0; i < bPtr; i++) {
        arr[left + i] = buffer[i];
    }
    delete[] buffer;
}