小编Uns*_*ure的帖子

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