Не могу понять, как могут работать рекурсивные функции без оператора возврата в Python

Question

Привет, я борюсь с пониманием того, как рекурсия работает в Python. Я работаю в версии Python 3.5 в частности. Я изучал эту реализацию алгоритма сортировки слиянием в Python:

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Я не могу понять, как работает эта реализация, потому что функция MergeSort не имеет оператора возврата. Более того, результаты рекурсивных вызовов MergeSort в верхней части тела функции не присваиваются переменным lefthalf и rightthalf. Поэтому я не могу понять, как можно настроить объединяющуюся часть для работы с этой реализацией. Когда я запускаю этот код в моем Python, конечно, он работает правильно. Я полагаю, что я не правильно понимаю замыкания в Python, но было бы здорово, если бы кто-то мог указать мне правильное направление. Заранее спасибо!

Вот версия, которая, как я понимаю, работает:

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        lefthalf = mergeSort(lefthalf)
        righthalf = mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)
    return(alist)

Answer 1

Сортировка слиянием работает в два этапа. Во-первых, он рекурсивно делит список пополам, пока не создаст списки с одним членом. В упомянутом вами коде if len(alist)>1: рекурсивно разбить список. На втором этапе он просто объединяет небольшие фрагменты в правильном порядке до тех пор, пока не будет создан первый список (но в порядке). Таким образом, на втором шаге сначала объединяются списки с одним членом, объединяются списки с двумя членами и так далее. while i < len(lefthalf) and j < len(righthalf):, while i < len(lefthalf): и while j < len(righthalf): части в коде объединяют части.

Answer 2

Могу ли я порекомендовать вставить ваш код здесь: http://pythontutor.com/visualize.html#mode=edit

И затем нажмите «Визуализировать выполнение».Вы увидите, как работает ваш код и каково состояние каждой переменной после каждой строки.

Answer 3

python передает списки по ссылке, то есть исходный список может быть изменен функцией, которой этот список был задан в качестве параметра, поэтому при вызове функции с помощью:

mergeSort(lefthalf)
mergeSort(righthalf)

lefthalf и righthalf сами отсортированы, обратите внимание, что внешний вызов mergeSort() также предполагает, что исходный список был изменен, он не возвращает новый отсортированный список, поскольку я сказал, что сортирует существующий список