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

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合并排序:0.6s

大名单:merge_sort:29.0smergeSort: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