java - 为什么合并排序在对反向排序列表进行排序时比普通排序列表更快？

Question

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

Answer 1

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

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

如果你要排序的列表的幂为2，那么正序和倒序应该没有区别。