为什么MergeSort的偶数分裂"更快"？

Question

MergeSort是一种分而治之的算法,它将输入分成几个部分并递归地求解这些部分.

...分离功能有几种方法.一种方法是拆分中间.这种方法有一些不错的属性,但是,我们将专注于一种更快一点的方法:奇偶分裂.我们的想法是将每个偶数位置元素放在一个列表中,将每个奇数位置放在另一个列表中.

这直接来自我的讲义.究竟为什么奇偶分裂比阵列中间快？

我猜测它与传递给MergeSort的列表有关,并且质量已经已经排序,但我不完全确定.

谁能对此有所了解？

编辑:我尝试在Python中运行以下内容...

global K
K = []
for i in range (1, 100000):
    K.append(i)


def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""

t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))

p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))

(MergeSort是奇数MergeSort,MergeSort2分为中心)

结果是:

0.771506746608

0.843161219237

Answer 1

我可以看到，它可能会更好，因为将其与替代元素分开意味着您不必知道输入从多长时间开始 - 您只需取出元素并将它们放入交替列表中，直到用完为止。

此外，如果您小心地允许更好的并行处理，您可能会在完成第一个列表的迭代之前开始分割结果列表。

我应该补充一点，我不是这些问题的专家，它们只是想到的事情......