如何迭代地编写合并排序？

Question

我写了一个递归版的合并排序.它使用了一个单独的merge例程:

def merge(lst1, lst2):
    i = j = 0
    merged = []
    while i < len(lst1) and j < len(lst2):
        if lst1[i] <= lst2[j]:
            merged.append(lst1[i])
            i += 1
        else:
            merged.append(lst2[j])
            j += 1
    merged.extend(lst1[i:])
    merged.extend(lst2[j:])
    return merged

def merge_sort(lst):
    if len(lst) < 2:
        return lst
    else:
        middle = len(lst) / 2
        return merge(merge_sort(lst[:middle]), merge_sort(lst[middle:]))

为了节省堆栈空间(以及为了解决/学习算法的纯粹乐趣),我试图以迭代的方式编写这个函数.但是,我发现这很困难,因为我不确定如何在最后组合不同的列表.

谢谢!

Answer 1

您将需要一个将被重复调用的merge函数（相同或几乎相同的函数）。merge因此，您无需更改该merge功能。

这是一个多遍解决方案。从块大小 2 开始，并在每次传递中将块大小加倍。

在每次传递中，将列表划分为大小不重叠的块。将每个块分成 2 部分并调用merge2 部分。

这是一个自下而上的版本。