这是合并排序的正确实现吗？

Question

def merge(arr1, arr2):
    returned = []
    while len(arr1) > 0 and len(arr2) > 0:
        if arr1[0] >= arr2[0]:
            returned.append(arr2[0])
            arr2.pop(0)
        else:
            returned.append(arr1[0])
            arr1.pop(0)
    if len(arr1) > 0:
        returned = returned + arr1
    if len(arr2) > 0:
        returned = returned + arr2
    return returned

上面是合并函数。下面是合并排序函数

def merge_sort(nums):
    #print("Merge sorting following array:")
    #print(nums)
    if len(nums) == 1:
        return nums
    else:
        middle = int(len(nums)/2)
        first_half = nums[:middle]
        #print("First half is:")
        #print(first_half)
        second_half = nums[middle:]
        #print("Second half is:")
        #print(second_half)
        return merge(merge_sort(first_half), merge_sort(second_half))

感觉好像有什么东西坏了，因为我用时间模块对它计时，它的速度大约是冒泡排序算法的4倍，在一个10个数字长的列表上。我想我可能对合并功能想得太多了，但我不能指出我做错了什么

Answer 1

您的实现基本上是功能性的，但它有一些缺点：

• 它无法处理空列表：这样的参数将导致无限递归，从而导致堆栈溢出。您应该测试长度是否为<；=1.
• merge函数通过反复弹出第一个元素来修改其参数。这可能是一种成本非常高昂的方法。使用索引变量在arr1和arr2中进行迭代会更有效
• 它没有实现稳定排序，因为相等元素首先从arr2获取，然后从arr1获取

以下是一个备选方案，您可以计时并比较：

def merge(arr1, arr2):
    result = []
    i = 0
    j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i = i + 1
        else:
            result.append(arr2[j])
            j = j + 1
    return result + arr1[i:] + arr2[j:]

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    else:
        middle = len(nums) >> 1
        first_half = nums[:middle]
        second_half = nums[middle:]
        return merge(merge_sort(first_half), merge_sort(second_half))