python - 缓慢的mergesort实现，怎么了？

我变得出乎意料了此合并排序实现的结果。与我的三向快速排序（也用python编写）相比，它非常慢。
！包括两个实现的源代码。
合并排序：

#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)

Quicksort:

#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

有人能想出一个解释或者甚至是一个解决办法吗？

最佳答案

递归合并排序并不是最好的方法。您应该使用直接迭代方法获得更好的性能。我对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++]

关于python - 缓慢的mergesort实现，怎么了？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3752926/