Простая ошибка сортировки слиянием в Python

Question

Я делаю назначение сортировки слиянием в Python, но у меня все еще есть ошибка RuntimeError: maximum recursion depth exceeded Вот мой код:

def merge_sort(list):
    left_num = len(list) // 2
    left_sorted = merge_sort(list[:left_num])
    right_sorted = merge_sort(list[left_num:])
    final_sort = merge(left_sorted, right_sorted)
    return final_sort

def merge(left_sorted, right_sorted):
    final_sort = []
    while left_sorted and right_sorted:
        if left_sorted[0] <= right_sorted[0]:
            final_sort.append(left_sorted[0])
            left_sorted.pop(0)
        else:
            final_sort.append(right_sorted[0])
            right_sorted.pop(0)
    final_sort = final_sort + left_sorted + right_sorted
    return final_sort

if __name__ == "__main__":
    list = [4, 2]
    print(merge_sort(list))

Может кто-нибудь сказать мне, почему? Чтобы сделать проблему более удобной для других, не стесняйтесь редактировать вопрос, чтобы сделать его более понятным. ^_^

Answer 1

Когда вы пишете рекурсивную функцию, вы должны быть осторожны с базовым случаем, который решает, когда рекурсия должна закончиться.

В вашем случае базовый вариант отсутствует. Например, если в списке есть только один элемент, вам не придется рекурсивно сортировать его снова. Итак, это ваше базовое условие.

def merge_sort(list):
    if len(list) == 1:
        return list
    ...
    ...

Примечание: имя переменной list затеняет встроенную функцию list, Поэтому лучше избегать использования встроенных имен.

---

Так как вы делаете много pop(0)s, стоит отметить, что он неэффективен в списках. Цитирование официальной документации Python,

Хоть list объекты поддерживают подобные операции, они оптимизированы для быстрых операций фиксированной длины и несут O(n) затраты на перемещение памяти для pop(0) а также insert(0, v) операции, которые изменяют как размер, так и положение основного представления данных.

Таким образом, лучшая альтернатива будет использовать collections.deque, вместоlist, если вы много хлопаете. Фактическое выскакивание изdeque сделано сpopleft метод.

>>> from collections import deque
>>> d = deque([4, 2])
>>> d.popleft()
4
>>> d
deque([2])

Answer 2

У вас нет точки выхода в merge_sort, Вам нужно сделать что-то вроде:

left_num = len(list) // 2
if left_num <= 1:
    return list

У вас всегда должен быть условный выход в функции рекурсии: if COND then EXIT else RECURSION_CALL,