algorithm - 为什么 MergeSort 的奇偶拆分为 'faster'？

Question

MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.

...There are several approaches for the split function. One way is to split down the middle. That approach has some nice properties, however, we'll focus on a method that's a little bit faster: even-odd split. The idea is to put every even-position element in one list, and every odd-position in another.

这直接来 self 的讲义。为什么奇偶拆分比数组中间的拆分更快？

我推测它与传递到 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

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

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

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