优化归并排序

Question

我正在练习归并排序，想知道我的第二个版本是否比第一个版本更好——因为在内存需求上看起来是更好的，因为我从列表中弹出元素，而不是仅仅移动索引。

版本 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 更好？我该如何描述这两个版本的内存需求呢？

Answer 1

对于一个列表 L，使用 L[:n] 这个操作在 Python 中需要 O(n) 的时间和 O(n) 的空间（它会创建一个包含 n 个元素的新列表）。

如果有三个列表 a、b 和 c，那么 a + b + c 的操作也是 O(n) 的时间和空间，其中 n 是 len(a) + len(b) + len(c)（同样会创建一个包含 n 个元素的新列表）。

因此，每次调用 mergesort() 都需要 T(n) = 2T(n/2) + O(n) 的时间和空间，也就是说，T(n) = O(n*log(n))。

你的第二个版本的时间复杂度更差，因为 left.pop(0) 这个操作是 O(len(left))。第二个版本的内存需求和第一个版本基本相同。

这里有一个时间复杂度为 O(n*log(n))，空间复杂度为 O(n) 的解决方案，结构相同（使用 Python 3.3+ 的语法）：

def mergesort(L):
    return list(merge_sort_gen(L, 0, len(L)))

def merge_sort_gen(L, start, n): # O(n*log(n)) time, O(n) space
    if n == 1:  # a list of one element is always sorted
        yield L[start]
    elif n > 1: # sort halves and merge them
        half = n // 2
        yield from merge(merge_sort_gen(L, start, half),
                         merge_sort_gen(L, start + half, n - half))

其中 merge() 函数用于合并两个已排序的迭代器。你可以使用 heapq.merge() 或者：

from functools import partial

def merge(sorted_a, sorted_b, done=object()): # O(n) time, O(1) space
    next_a, next_b = partial(next, sorted_a, done), partial(next, sorted_b, done)

    a, b = next_a(), next_b()
    while a is not done and b is not done:
        if b < a:
            yield b
            b = next_b()
        else:
            yield a
            a = next_a()

    item, rest = (a, sorted_a) if b is done else (b, sorted_b)
    yield item #XXX at least one of sorted_a or sorted_b must be non-empty
    yield from rest

你可以 在 Python Tutor 中逐步跟踪代码。

yield from iterable 产生的项目和以下内容相同（但内部细节不同）：

for item in iterable:
    yield item

请参见 Python 中 yield 关键字的解释。

Answer 2

为什么不使用collections里的双端队列（deque）呢？这样可以降低popleft()操作的成本。