python - 使用 Python 表示合并排序，如何避免 IndexError

Question

我知道这不对，我找到了another method没有无限数，但我仍然想知道是否可以使用无限数来纠正它。

def MergeSort(A):
    if len(A) > 1:
        mid = len(A) / 2
        left = A[0:mid]
        right = A[mid:]

        MergeSort(left)
        MergeSort(right)

        w = float("inf")
        left.append(w)
        right.append(w)
        i,j = 0,0
        for k in range(len(A)):
            if left[i] <= right[j]:
                A[k] = left[i]
                i += 1
            else:
                A[k] = right[j]
                j += 1  

Answer 1

问题出在 for k in range(len(A)): 循环中；当您用尽 left 中的所有值但 right 中仍有值时会发生什么(反之亦然)？

链接方法添加了一个基本上看起来像的测试

if (left still has values) and ((right has no values) or (next_left < next_right)):
    take a value from left

您上面的代码反而添加了一个守卫值，确保如果您位于左侧守卫值，则它保证大于任何非守卫右侧值(反之亦然)。在 for 循环停止之前，情况一直如此，左右各只包含保护值。

另一个选项，as seen here , 就是一直循环，直到左边或右边都用完，然后有后续循环收集剩余的值。