为什么我的归并排序比这个归并排序慢？

Question

我已经在 C/C++ 中实现了合并排序。但是我的代码比我从网站上提取的代码花费的时间更长。

这两种情况的递归代码似乎完全相同：

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

但是 merge 算法有点不同，但我看不出这里有什么显着差异。

我的合并算法 :

void merge(int *arr, int l, int mid, int h) {
    int i = l, j = mid+1, k = l;
    int* newSorted = new int[h+1]();
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            newSorted[k++] = arr[i++];
        else
            newSorted[k++] = arr[j++];
    }
    for (; i <= mid; i++)
        newSorted[k++] = arr[i];
    for (; j <= h; j++)
        newSorted[k++] = arr[j];
    k = 0;
    for (int x = l; x <= h; x++)
        arr[x] = newSorted[x];
    delete[] newSorted;
}

200000（二十万输入）所用时间：

17 Seconds

来自网站的合并算法：

void merge(int arr[], int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;

    int* L = new int[n1];
    int *M = new int[n2];
    

    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];


    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }


    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
    delete[] L;
    delete[] M;
}

200000（二十万输入）所用时间：

0 Seconds

时间上有很大的不同。我不明白我的代码中的问题。如果有人能帮我解决这个问题，我将不胜感激。谢谢。

Answer 1

您的算法需要为每个步骤分配 [h+1]。

来自网站的算法只需要分配[r-p+1] （你的 h = 它的 r，你的 l = 它的 p）

为什么我的归并排序比这个归并排序慢？

Why is my merge sort slower than this merge sort?

c++

sorting

merge

mergesort