缓慢的归并排序实现，问题出在哪？

Question

我在这个归并排序的实现上得到了意想不到的结果。它的速度比我写的三路快速排序慢得多（也是用Python写的）。

我的快速排序处理10000个元素大约只需要0.005秒，而归并排序却需要1.6秒！这里附上了两个实现的源代码。

归并排序：

#Merges two sorted lists into one sorted list. recursively
def merge(left, right):
    if len(left) == 0 and len(right) == 0:
        return []
    elif len(left) == 0:
        return right
    elif len(right) == 0:
        return left
    else:
        if left[0] <= right[0]:
            return left[:1] + merge(left[1:],right)
        else:
            return right[:1] + merge(left,right[1:])

#Splits a list in half and returns the halves
def halve(list):
    return list[:len(list)//2],list[len(list)//2:]

#Mergesort
def mergesort(list):
    if len(list) <= 1:
        return list
    left,right = halve(list)
    left,right = mergesort(left),mergesort(right)
    return merge(left,right)

快速排序：

#Three-way QuickSort in Python
def quicksort(a):
    if len(a) == 0:
        return []
    p = a[(len(a)-1)//2]
    less = quicksort([x for x in a if x < p])
    greater = quicksort([x for x in a if x > p])
    equal = [x for x in a if x == p]
    return less + equal + greater

有没有人能给出一个解释，或者甚至是一个解决办法？

Answer 1

解释：

一般来说，快速排序在实际使用中比其他Θ(nlogn)的算法要快得多。这是因为它的内部循环可以在大多数计算机架构上高效地实现。而且在大多数真实的数据中，我们可以做一些设计上的选择，来减少需要花费较长时间（即平方时间）的可能性。

Answer 2

关于性能的猜测通常是不准确的，但我还是想分享一下我的经验。如果你真的想了解，可以进行性能分析：

你在合并列表，比如用 left[:1] + merge(left[1:],right) 这种方式，这在Python中是比较慢的操作。因为它会从两个列表中创建一个新的列表，所以你的归并排序会产生大约 N**2 个中间列表。而快速排序则使用非常快速的列表推导（LC），创建的列表要少得多（我记得大约是 2N 左右）。

试试用 extend 来代替 +，也许会有所帮助。

Answer 3

递归的归并排序其实不是最好的方法。用简单的循环方式会有更好的性能。我对Python不太熟悉，所以我会给你一个类似C语言的伪代码。

ileft = 0 // index into left array
iright = 0 // index into right array
iresult = 0 // index into result array
while (ileft < left.length && iright < right.length)
{
    if (left[ileft] <= right[iright])
        result[iresult++] = left[ileft++]
    else
        result[iresult++] = right[iright++]
}

// now clean up the remaining list
while (ileft < left.length)
    result[iresult++] = left[ileft++]

while (iright < right.length)
    result[iresult++] = right[iright++]