为什么合并排序比正常排序列表排序更快？

我正在做一个基于比较的合并分析算法，它按照升序输出。我注意到它是更快（比较少），当我给它一个反向排序列表，而不是升序排序列表。有人可以解释为什么吗？为什么合并排序比正常排序列表排序更快？

来源

2012-08-28 Scott Mullaly

http://stackoverflow.com/q/11227809/758280 – Jeffrey

@Jeffrey我假设他正在计算比较的次数（他写的“比较少”），这应该排除分支预测。 –

我其实只是有同样的情况，其中比较的数量恰好是在倒序数组上的数组长度。随机数组和排序数组的比较次数遵循n（log（n））模式。 –

您的排序代码中必须有错误。

根据我的理解，通过文字MergeSort执行的比较次数应该是独立的的数据。这意味着它不能比O(n log n)差，但也不会更好（除非你做了一些聪明的修改，比如在“自然mergesort”或TimSort中）。

来源

2012-08-28 22:05:50

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

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

如果你想排序的列表是2的效价，正常顺序和逆序之间应该没有区别。

来源

2015-05-17 13:17:52

为什么合并排序比正常排序列表排序更快？

回答

相关问题