递归调用归并排序算法

Question

我刚接触递归算法，目前正在编写一个归并排序算法，该算法比较两个列表的第一个元素，并确定哪个元素更小，然后将较小的元素添加到新列表中。

我试图在每次比较后更新三个列表，并使用更新后的列表再次调用函数本身，但是我在Pycharm中遇到了未解决的引用问题，不确定自己做错了什么。这是我的代码，我期望的输出结果是:

new_list = [4, 8, 15, 16, 23, 42, 50, 75, 108]

def merge_Sort(list1, list2, new_list):
    list1 = [8, 15, 16, 50, 75]
    list2 = [4, 23, 42, 108]
    new_list = []
    for i in range(len(list1)):
            if list1[0] < list2[0]:
                new_list = new_list.append(list1[0])
                list1 = list1.remove(list1[0])
                break


            elif list1[0] > list2[0]:
                new_list = new_list.append(list2[0])
                list2 = list2.remove(list2[0])
                break

    merge_Sort(list1, list2, new_list)

merge_Sort(list1, list2, new_list)

- Perplexityy

---

不确定为什么会被点踩。代码中有明显的合理尝试，并且问题已经得到了清晰的解释。 - Darren Haynes

Answer 1

你的代码导致了无限递归。你应该将 list1，list2 和 new_list 的初始化移到 merge_Sort 函数之外。

def merge_Sort(list1, list2, new_list):
    for i in range(len(list1)):
        if list1[0] < list2[0]:
            new_list.append(list1[0])
            list1.remove(list1[0])
            break
        elif list1[0] > list2[0]:
            new_list.append(list2[0])
            list2.remove(list2[0])
            break

    merge_Sort(list1, list2, new_list)

list1 = [8, 15, 16, 50, 75]
list2 = [4, 23, 42, 108]
new_list = []
merge_Sort(list1, list2, new_list)

- kvorobiev

---

谢谢，现在它可以运行了。现在它告诉我“NoneType”对象不可订阅，并且我在第一个if语句的那一行收到了错误。这里可能会评估为无。 - Perplexityy

@Perplexityy：list.append 方法会改变列表；这是 Python 的惯例，这样的方法不会返回对已更改对象的引用，而是返回 None。.remove 方法也适用类似的说明。因此，您的代码（以及 kvorobiev 版本）会破坏您的各种列表，将它们替换为 None。 - PM 2Ring