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

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))

是否有可能使其成为一种动态的在同时循环，而每个左和右数组分成两个，一种指针根据左和右数组的数量不断增加并打破它们，直到只剩下单个长度大小的列表？因为每次在左和右侧进行下一次拆分时，数组都会不断分解，直到只剩下单个长度列表，因此左侧（左-左，左-右）和右侧（右-左，右-右）中断的数量将增加，直到它达到所有大小为1的列表。

Answer 1

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

欲了解更多信息，您可以阅读本文，或参考Robert Laver的“Java中的数据结构和算法”中名为“消除递归”的部分（尽管本书中的所有示例都是Java给出的，但很容易掌握主要思想）。

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

一种可能的实现方式可能是：

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 []

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