迭代归并排序？

Question

我知道通过合并对某些内容进行排序的经典递归方法。它产生了O(n * log(n))复杂性，可以通过递归关系或多或少地容易地表示出来。

我尝试以迭代方式重新实现归并排序：

def atomize(l):
    return list(
        map(
            lambda x: [x],
            l if l is not None else []
        )
    )

def merge(l, r):
    res = []
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = []
        elif len(r) < 1:
            res += l
            l = []
        else:
            if l[0] <= r[0]:
                res.append(l.pop(0))
            else:
                res.append(r.pop(0))
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.pop(0), atoms.pop(0)))
    return atoms[0]

……总觉得哪里搞错了，又没注意准确的地方。递归合并排序会拆分问题，除非未排序值列表简化为单例列表 - 可以比较的单个元素。这就是这样atomize(...)做的：给定一个列表，生成一个列表-单例（顺序O(n)）列表。

显然，merge(...)也是O(n)：暂时忽略没有链接列表用于连接，这在这里并不重要。

最后..本身的while块iter_merge_sort(...)完全n - 1重复，每次最多花费O(n). 因此，我采用了O(n * log(n))算法并将其“改进”为(n - 1) * n ~ O(n * n). 我的错误在哪里？

Answer 1

你的算法是完全正确的。问题在于，您使用的list.pop(0)是一种出队方式，这在 Python 中的成本为O(n)，因为列表中弹出项目之后的所有项目都必须复制到前面的位置。

您可以使用collections.deque代替列表，以便可以使用该deque.popleft方法，该方法的成本为O(1)：

from collections import deque

def atomize(l):
    return deque(
        map(
            lambda x: deque([x]),
            l if l is not None else []
        )
    )

def merge(l, r):
    res = deque()
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = deque()
        elif len(r) < 1:
            res += l
            l = deque()
        else:
            if l[0] <= r[0]:
                res.append(l.popleft())
            else:
                res.append(r.popleft())
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.popleft(), atoms.popleft()))
    return list(atoms[0])

以便：

iter_merge_sort([3,5,1,6,2,1])

返回：

[1, 1, 2, 3, 5, 6]