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

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循环中使它成为一种动态,而每个左右数组都分成两个,一种指针根据左右数组的数量不断增加并打破它们直到只剩下单个长度的列表？因为每当下一次分割进入左右两侧时,阵列就会不断分解,直到只剩下单个长度列表,因此左侧(左 - 左,右 - 右)和右侧(右 ​​- 左,右 - 右)中断将增加,直到达到所有大小为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 []

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