解释了两种不同合并排序实现之间的比较

Question

我这样写我的实现：

def merge_sort(lst):
    if len(lst) < 2: return lst

    midx = len(lst) // 2

    return merge(
        merge_sort(lst[:midx]),
        merge_sort(lst[midx:])
    )

def merge(left, right):
    merged_lst = []
    while left and right:
        merged_lst.append((left.pop(0) if left[0] <= right[0] else right.pop(0)))

    merged_lst.extend(left if left else right)
    return merged_lst

然后我在网上找到了这个：

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

我以为我的速度会更快，但会占用更多内存。然后我分析了 med_lst 和 big_lst:

med_lst = [random.random() for _ in range(100000)]
big_lst = [random.random() for _ in range(500000)]

在 Jupyter notebook 中使用结构如下的代码：

printmd(f'RAM at start: {memory_profiler.memory_usage()[0]:0.1f}MiB', color='blue')
t1 = time.time()
printmd(f'Sorting: {len(big_lst)} elements', color="blue")
merge_sort(big_lst)
t2 = time.time()
printmd(f'RAM after sorting list: {memory_profiler.memory_usage()[0]:0.1f}MiB, took {t2 - t1:0.1f}s', color='blue')

时间复杂度让我吃惊：

中等列表： merge_sort: 1.2s mergeSort: 0.6s

大名单： merge_sort: 29.0 秒 mergeSort: 3.4s

这是否意味着只是因为创建了一个新列表，并且可能发生冲突或调整大小？还是我的实施/思考过程有误（菜鸟错误——这个答案得 0 分）？我认为我的功能仍然是 0(nlogn)，但是随着集合变大，您真的可以说它们是“可比的”吗

我没有逐行分析这一点，因为它更基础

Answer 1

正如@CH在评论中指出的，前面的pop()是罪魁祸首。

通过在弹出之前反转列表然后在弹出之后反转，我设法使我的实现实际上比另一个实现更快：

def merge(left, right):
    merged_lst = []
    if left: left.reverse()
    if right: right.reverse()
    while left and right:
        merged_lst.append((left.pop() if left[-1] <= right[-1] else right.pop()))
    if left: left.reverse()
    if right: right.reverse()
    merged_lst.extend(left if left else right)
    return merged_lst

中等列表：merge_sort：0.5s mergeSort：0.7s

大名单：merge_sort：2.6s mergeSort：4.0s

解释了两种不同合并排序实现之间的比较

Comparison between two different merge sort implementations explained

python

complexity-theory

mergesort