改进归并排序 [英] Improving merge sort

问题描述

我在练归并排序，并很好奇，如果我的第二个版本比第一次好 - 它似乎是在对内存要求方面，因为我从列表弹出，而不是只动指数

I am practicing merge sort and am curious if my second version is better than the first -- it seems to be in terms of memory requirement since I am popping from a list instead of just moving indices

版本1：

def mergesort(L):
    if len(L)<=1: return L
    pivot=len(L)/2
    left=mergesort(L[:pivot])
    right=mergesort(L[pivot:])
    i=j=0
    sortedArr=[]
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            sortedArr.append(left[i])
            i+=1
        else:
            sortedArr.append(right[j])
            j+=1
    return sortedArr + left[i:] + right[j:]

2版

def mergesort(L):
    if len(L)<=1: return L
    pivot=len(L)/2
    left=mergesort(L[:pivot])
    right=mergesort(L[pivot:])
    sortedArr=[]
    while left!=[] and right!=[]:
        if left[0]<right[0]:
            sortedArr.append(left.pop(0))
        else:
            sortedArr.append(right.pop(0))
    return sortedArr + left + right

没有进入并行化，有没有办法在第2版，以进一步提高，假设它是优于第1版？如何我会形容这两个版本的内存要求为止？

Without getting into parallelizing, is there any way to further improve upon Version 2, assuming it is superior to Version 1? How would I describe the memory requirements of these two versions so far?

推荐答案

为什么不利用集合一个deque？这将降低popleft（）操作的成本是多少？

why not using a deque from collections ? It would lower the cost of the popleft() operation ?

这篇关于改进归并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！