改进归并排序

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更好，有没有办法进一步改进版本2？到目前为止，我该如何描述这两个版本的内存需求？

Answer 1

为什么不使用集合中的双人队列呢？它会降低popleft()操作的成本吗？

Answer 2

对于list 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)) 3.3+语法)的Python，O(n)空间解决方案：

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

你可以使用follow the code step by step at Python Tutor。

yield from iterable生成的项目与相同(但内部细节不同)：

for item in iterable:
    yield item

参见The Python yield keyword explained。