迭代合并排序？

Question

我知道通过合并来排序的经典递归方法。 它产生O(n * log(n))复杂度，可以通过递归关系或多或少地显示出来。在

我尝试以迭代的方式重新实现merge sort：

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)：忽略并没有链表用于连接，这在这里并不重要。在

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

Answer 1

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

您可以使用collections.deque代替list，这样就可以使用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])

因此：

^{pr2}$

退货：

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