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

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);
}
}

然而合并算法有点不同，但我看不出有什么显著的区别。

我的合并算法:

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秒网站合并算法:

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秒时间上有很大的差异。我不明白我代码中的问题。如果有人能帮我解决这个问题，我会很感激的。谢谢你。

Answer 1

你的算法需要为每一步分配[h+1]。

算法从一个网站只需要分配[r-p+1](你的h = r，你的l = p)