缓慢的mergesort实现,有什么不对？

Question

我从这个mergesort实现得到意外(？)结果.与我的三向快速排序(也用python编写)相比,它非常慢.

我的quicksort在大约0.005s后完成10000个元素,而mergesort需要1.6s!包括两个实现的源代码.

归并:

#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

关于性能的猜测通常是错误的,但我会用这个一次,因为我对此有一些经验.简介如果你真的想知道:

您正在添加列表,即left[:1] + merge(left[1:],right),这是Python中较慢的操作之一.它会从两个列表中创建一个新列表,因此您的mergesort会创建类似N**2的中间列表.另一方面,快速排序使用非常快的LC而创建更少的列表(我认为像2N左右).

尝试使用extend而不是+,也许这有帮助.