替代基于递归的合并排序逻辑

Question

这里是python中的合并排序逻辑：(这是第一部分，忽略函数merge())问题的关键是将递归逻辑转换为while循环。代码提供：Rosettacode合并排序

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) / 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

当每个左数组和右数组分解为两个数组时，是否有可能使其成为list循环中的一种动态类型，一种指针根据左数组和右数组的数量不断增加，直到只剩下一个长度大小的列表为止？因为每次下一次分割同时出现在左边和右边时，数组一直在分解，直到只剩下一个长度列表，所以左(左、左、右)和右(右、左、右)断点的数目都会增加，直到达到一个大小为1的列表。

Answer 1

一个可能的实现可能是：

def merge_sort(m):
    l = [[x] for x in m]                  # split each element to its own list
    while len(l) > 1:                     # while there's merging to be done 
        for x in range(len(l) >> 1):      # take the first len/2 lists
            l[x] = merge(l[x], l.pop())   # and merge with the last len/2 lists
    return l[0] if len(l) else []

递归版本中的堆栈帧用于存储需要合并的越来越小的列表。您正确地识别出，在堆栈的底部，对任何排序中的每个元素都有一个元素列表。因此，通过从一系列的单元素列表开始，我们可以迭代地构建更大的合并列表，直到我们有了一个单一的排序列表。

Answer 2

应读者要求从替代基于递归的合并排序逻辑转发：

消除递归的一种方法是使用队列来管理出色的工作。例如，使用内置的collections.deque

from collections import deque
from heapq import merge

def merge_sorted(iterable):
    """Return a list consisting of the sorted elements of 'iterable'."""
    queue = deque([i] for i in iterable)
    if not queue:
        return []
    while len(queue) > 1:
        queue.append(list(merge(queue.popleft(), queue.popleft())))
    return queue[0]

Answer 3

据说，每个递归函数都可以用非递归的方式编写，所以简单的回答是:是的，这是可能的。我能想到的唯一解决方案就是使用基于堆栈的方法。当递归函数调用自身时，它会在内部堆栈上放置一些上下文(参数和返回地址)，这对您来说是不可用的。基本上，为了消除递归，您需要做的是编写自己的堆栈，每次进行递归调用时，都将参数放到这个堆栈上。

要获得更多信息，您可以阅读这篇文章，或者参考Robert的“Java和Algorithms”中的“消除递归”一节(尽管本书中的所有示例都是用Java提供的，但很容易理解主要思想)。