合并排序的效率差，不受编译器优化影响

Question

在尝试测量各种排序算法的时间需要对无符号整数的随机数组进行分类时，我获得了一些关于自上而下合并排序的特殊行为，这些行为似乎并非由不良的实现引起。

在长度高达100万个值的阵列上，合并排序的行为比随机pivot QuickSort甚至外壳排序都最差。这是出乎意料的，所以我尝试了多个在线合并Sort的实现，但是结果似乎仍然大致相同。

图1，优化

这是我用于这些图形的实现：

void merge(int *array, int l, int m, int r) {
    int i, j, k, nl, nr;
    nl = m - l + 1; nr = r - m;
    int *larr = new int[nl], *rarr = new int[nr];

    for (i = 0; i < nl; i++)
        larr[i] = array[l + i];
    for (j = 0; j < nr; j++)
        rarr[j] = array[m + 1 + j];

    i = 0; j = 0; k = l;
    while (i < nl && j < nr) {
        if (larr[i] <= rarr[j]) {
            array[k] = larr[i];
            i++;
        }
        else {
            array[k] = rarr[j];
            j++;
        }
        k++;
    }
    while (i < nl) {
        array[k] = larr[i];
        i++; k++;
    }
    while (j < nr) {
        array[k] = rarr[j];
        j++; k++;
    }

    delete[] larr;
    delete[] rarr;
}

void mergeSort(int *array, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

我也尝试过删除编译器的优化（可视++ 15），偏爱尺寸而不是速度，这似乎影响了所有其他算法而不是合并排序。尽管如此，它仍然是最糟糕的。

图2，优化

唯一的时间合并排序没有给出最糟糕的时间用1500万个元素的阵列进行测试，其性能比堆的阵列要好得多，但与其他元素相去甚远。

我绘制的值是带有随机数组的100个测试的平均值，因此我认为这只是一种特殊情况。我也认为在合并中使用动态内存是这些结果的原因，这些测试和其他所有内容都足够了。

有人知道为什么合并排序行为如此糟糕吗？为什么编译器优化似乎不会影响合并排序？