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

Question

这里是python中的归并排序逻辑:(这是第一部分，忽略函数merge())问题的重点是将递归逻辑转换为while循环。代码礼貌:Rosettacode Merge Sort

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

是否有可能在 while 循环中使其成为一种动态的，当每个左右数组分成两部分时，一种指针根据左右数组的数量不断增加并打破它们直到只有单一长度大小名单还剩下？因为每次在左侧和右侧进行下一次拆分时，数组都会不断分解，直到只剩下单个长度列表，所以左侧 (left-left,left-right) 和右侧 (right-) 的数量left,right-right) breaks 将增加，直到它达到所有大小为 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 []

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