java - 为什么归并排序在排序反向排序列表时比正常排序列表更快？

Question

我正在对按升序输出的合并排序算法进行基于比较的分析。我注意到当我给它一个反向排序的列表而不是一个升序排序的列表时它更快（比较少）。谁能解释为什么？

Answer 1

要合并两个长度为 M 和 N 的列表，您最多需要 M+N-1 个比较。如果第一个列表中的所有条目都小于第二个列表中的条目，则只需进行 M 次比较。如果第二个列表中的所有条目都小于第一个列表中的条目，则只需进行 N 次比较。

如果您要排序的数字总数不是 2 的效力，那么您将遇到分成两个不同长度的列表的情况。我怀疑您以这两个中的第一个具有更多元素的方式实现了合并排序。这意味着该分区和合并的 M = N+1。如果您的元素顺序相反，则第二个列表的所有元素都将小于第一个列表的元素，并且在正确顺序的情况下您将需要 N 比较而不是 M。

如果您要排序的列表的效力为 2，则正常顺序和反向顺序之间应该没有区别。

Answer 2

您的排序代码中一定有错误。

据我了解，文字 MergeSort 执行的比较次数应该与数据无关。这意味着它不能比 更差O(n log n)，但也不能更好（除非你做了一些聪明的修改，比如在“自然归并排序”或 TimSort 中）。

Answer 3

使用自上而下的合并排序实现，升序排序的列表不会经过下面代码中的 merge() 步骤。因此，它是最快的。此外，反向排序列表会跳过 merge() 步骤中的某些比较步骤。例如，它没有进入我的代码下面的比较行。

else if (comp(aux[j], aux[i])) a[k] = aux[j++];     // B[j] <  A[i], take B[je

因此，它也比遍历所有代码的随机排序列表更快。

供你参考：

void merge(int *a, int *aux, int lo, int mi, int hi, bool (*comp)(int, int)) {
    assert(sorted(a, lo,   mi, comp));      // precondition: a[lo..mi]   sorted
    assert(sorted(a, mi+1, hi, comp));      // precondition: a[mi+1..hi] sorted
    for (int k = lo; k <= hi; k++)  aux[k] = a[k];

    int i = lo;
    int j = mi + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mi)       a[k] = aux[j++];     // A is exhausted, take B[j]
        else if (j > hi)  a[k] = aux[i++];     // B is exhausted, take A[i]
        else if (comp(aux[j], aux[i])) a[k] = aux[j++];     // B[j] <  A[i], take B[j]
        else                           a[k] = aux[i++];     // A[i] <= B[j], take A[i]
    }
    assert(sorted(a, lo, hi, comp));        // postcondition: a[lo..hi] sorted
}

void mergesort(int *a, int *aux, int lo, int hi, bool (*comp)(int, int)) {
    if (hi <= lo) return;
    int mi = lo + (hi - lo) / 2;
    mergesort(a, aux, lo,     mi, comp);
    mergesort(a, aux, mi + 1, hi, comp);
    
    if (comp(a[mi], a[mi + 1])) return;  // already sorted
    merge(a, aux, lo, mi, hi, comp);
}

（债务人）<><