MergeSort without merge function ,,这个算法如何合并列表

Question

def mergeSort(A): 
    if len(A) < 2: 
     return A 

    mid = int(len(A)/2) 
    left = mergeSort(A[:mid]) 
    right = mergeSort(A[mid:]) 

    r,l = 0,0 
    B = [] 

    while len(B) < len(A): 
     if r >= len(right) or (l < mid and left[l] < right[r]): 
      B.append(left[l]) 
      l += 1 
     elif r < len(right): 
      B.append(right[r]) 
      r += 1 

    return B 

print(mergeSort([4,3,6,9,8,5,1])) 

我对上述程序的怀疑是如何在没有单独的合并函数的情况下合并列表？

到底递归函数调用后，我觉得left和right列表包含每个只有一个元素......他们进行排序，并插入使用while循环列出B ......那么其他的元素..因为在这里while循环只执行一次，以及如何将列表A再次分割和合并...我在互联网上获得了这个程序，它工作得很好。

Answer 1

我认为您的问题是您不明白递归如何工作。 while循环不仅执行一次，而且每次（非平凡）递归调用执行一次。

这是值得通过操作跟踪。无论是在纸上，在调试器中使用this one这样的图形化可视化工具，还是只使用一堆print调用，都是您真正了解到底发生了什么的唯一方法。

我认为图形化可视化器会更容易遵循，但学习如何在纸上做到这一点是值得的，所以让我们来做。我们只需要通过一个非平凡的合并，因为在那之后它们看起来都是一样的。

• 排序[4,3,6,9,8,5,1]
  • 排序[4,3,6]
  • 排序[4]
  • 由于[4]长度为0或1，平凡排序它通过只返回它原样。
  • 排序[3, 6]
  • 排序[3]
    • 由于[3]长度为0或1，平凡排序它通过只返回它原样。
  • 排序[6]
    • 由于[6]长度为0或1，平凡排序它通过只返回它原样。
  • 合并排序[3]和[6]半部（如果您使用图形可视化，这发生在步骤31;如果使用调试器，将断点处线12，这将在第一时间断点是命中）：
    • 开始l, r, B = 0, 0, []
    • 由于len([]) < len([3, 6])，我们还没有完成。
    • 由于第一个if条件成立，因此从left开始追加并且递增l，因此l, r, B = 1, 0, [3]。
    • 由于len([3]) < len([3, 6])，我们没有完成。
    • 由于第一个if条件为假，第二个为真，从right追加并增加r，所以l, r, B = 1, 1, [3, 6]。
    • 由于len([3, 6]) == len([3, 6])，我们完成了。
  • 将排序后的[4]和[3, 6]合并为上述的相同方式。
• 排序[9, 8, 5, 1]。
  • 这正好在与上述相同，并将包括平凡返回4单元素列表，加上使用while环合并[9]和[8]，和[5]和[1]，和[8, 9]沿途[1, 5];如果你不明白它是如何工作的，你可以自己一步步细节。
• 将排序的[3, 4, 6]和[1, 5, 8, 9]合并为上述的相同方式。

正如您所看到的，while循环实际上执行了六次，而不仅仅是一次。

Answer 2

执行while循环之前，我们有两个有序列表中left和right 什么while循环的作用是要经过在列表中left和right顺序每个元素并插入较小的元素融入到一个空列表B，和它由mergesort函数返回。

我们不需要调用单独

合并功能，例如，考虑列表[3,1,2] 的通话将是：

mergesort([3,1,2]) 
left = mergesort([3]) -> [3] 
right = mergesort([1,2]) -> [1,2] #magically 

B = [] 

while循环采l次/ r左/右的元素取决于哪一个较小，并且分别递增l/r，并将该元素插入B

B -> [1,2,3] 

尝试在纸上运行mergesort（[1,2]）的while循环以了解right如何变为[1,2]