在Python中找出归并排序的中间点

Question

我编写了两种不同的归并排序算法实现，只有一个区别，即用于查找数组中点来划分数组的公式。

第一次实现：（正确运行）

def mergesort(arr):
    start = 0
    end = len(arr) - 1
    if len(arr) > 1:
        mid = int(len(arr)/2)
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])
        return merge(left,right)
    else:
        return arr

def merge(left,right):
    final = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                final.append(left[0])
                del left[0]
            elif right[0] < left[0]:
                final.append(right[0])
                del right[0]
        elif len(right) > 0:
            final.extend(right)
            right = []
        elif len(left) > 0:
            final.extend(left)
            left = []
    return final


arr = list(map(int,input().split(' ')))
print ("List before sorting:",arr)
final = mergesort(arr)
print ("After sorting:",final)

第二次实现（进入无限循环）：

def mergesort(arr):
    start = 0
    end = len(arr) - 1
    if len(arr) > 1:
        mid = int(start + (end - start)/2)
        left = mergesort(arr[:mid])
        right = mergesort(arr[mid:])
        return merge(left,right)
    else:
        return arr

def merge(left,right):
    final = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                final.append(left[0])
                del left[0]
            elif right[0] < left[0]:
                final.append(right[0])
                del right[0]
        elif len(right) > 0:
            final.extend(right)
            right = []
        elif len(left) > 0:
            final.extend(left)
            left = []
    return final


arr = list(map(int,input().split(' ')))
print ("List before sorting:",arr)
final = mergesort(arr)
print ("After sorting:",final)

我已经看到了快速排序算法中使用的第二个公式。问题是，如果我的目标是划分数组（如快速排序的情况），为什么它会进入无限循环。

我很困惑，无法得出任何合乎逻辑的结论。

有人可以解释一下这个问题吗？提前非常感谢。

Answer 1

在处理单个数组而不是子数组的多个实例时，应使用第二种方法。原始数组不是使用实际的单独子数组，而是通过索引范围拆分为逻辑子数组。 mergesort 函数需要 3 个参数，mergesort(arr, start, end)，调用者将调用 mergesort(arr, 0, len(arr))。 merge 函数需要 4 个参数，merge(arr, start, mid, end)。

使用带有一个参数的输入函数 mergesort(arr) 可以提高效率。它将分配一个工作数组 tmp 并将其传递给内部函数，mergesort(arr) 的调用将是 mergesort(arr, tmp, 0, len(arr))。合并排序函数将是 mergesort(arr, tmp, start, end)。合并函数将是 merge(arr, tmp, start, mid, end)。

Answer 2

（数组起始索引 +（数组结束索引 - 数组起始索引）/2）