Реализация сортировки слиянием в Python

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

Это то, что вы видите в своем отладчике во время рекурсивных вызовов. На первом уровне рекурсии lefthalf создается путем копирования некоторых значений из исходного списка (с синтаксисом среза). Он начинается с [54, 26]. Затем этот список передается другому вызову mergesort. Обратите внимание, что наименование может сбивать с толку, так как во внутреннем вызове оно обращается к списку как alist (и у него есть собственный отдельный список lefthalf). Когда внутренний вызов возвращается, содержимое lefthalf внешнего вызова оказывается измененным на [26, 54] (они в порядке, чего мы и хотим!).

Возможно, ваш отладчик не дает понять, когда происходит возврат. Поскольку это одна и та же функция (из-за рекурсии), может быть неочевидно, когда внутренний вызов завершается и возобновляется поток управления внешнего вызова.

Вот пошаговое руководство по вашему коду, в котором я показываю значения различных переменных на разных уровнях рекурсии, когда вы сортируете список примеров. Обратите внимание, что это не исполняемый код Python, я делаю отступ, чтобы указать уровень рекурсии, а не для потока управления. Чтобы пример был относительно коротким, я также опускаю некоторые шаги, такие как сравнение значений из двух подсписков и обновление индексов i j и k в процессе слияния:

plist = [54,26,93,17]
mergesort(plist)
    # alist is a referece to plist which contains [54,26,93,17]
    lefthalf = alist[:mid]  # new list which initially contains [54,26]
    righthalf = alist[mid:] # new list which initially contains [93,17]
    mergesort(lefthalf)
        # alist is a reference to the outer lefthalf list, which contains [54,26]
        lefthalf = alist[:mid]  # new list, initially contains [54]
        righthalf = alist[mid:] # new list, initially contains [26]
        mergesort(lefthalf)
            # alist is a reference to the previous level's lefthalf, [54]
            # the if statement doesn't pass its test, so we do nothing here (base case)
        # lefthalf was not changed by the recursive call
        mergesort(righthalf)
            # alist is a reference to the previous level's righthalf, [26]
            # base case again
        # righthalf was not changed
        alist[k]=righthalf[j] # now we merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i] # these statements change the contents of alist
    # lefthalf's contents changed, it is now sorted, [26,54]
    mergesort(righthalf)
        # alist is a reference to the outer righthalf list, which contains [93,17]
        lefthalf = alist[:mid]  # new list, initially contains [93]
        righthalf = alist[mid:] # new list, initially contains [17]
        mergesort(lefthalf) # base case, nothing happens (I'll skip the details)
        mergesort(righthalf) # base case, nothing happens
        alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i]  # we change the contents of alist to [17,93]
    # righthalf's contents changed, it is now sorted, [17,93]
    alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist (more steps)
    alist[k]=lefthalf[i]
    alist[k]=lefthalf[i]
    alist[k]=righthalf[j] # after these statements, alist is [17,26,54,93]
# plists's contents are changed so it contains [17,26,54,93]

Это может помочь вам немного отступить от этой сложной рекурсивной ситуации и посмотреть на более простой пример, чтобы убедиться, что вы понимаете, как списки могут быть видоизменены:

a = [1, 2] # create a list object with some initial contents

b = a      # b refers to the same list object as a, nothing is copied
b[1] = 3   # this modifies the list object itself, replacing the 2 with a 3

print(a)   # prints [1, 3] even through we're looking at a rather than b

def func(lst): # lst will be a new name bound to whatever is passed to the function
    lst[1] = 4 # we can modify that passed-in object (assuming it's the right type)

func(a)    # lst in the function will become another name for the list object
print(a)   # prints [1, 4]

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

Таким образом, обновление вашего списка происходит каждый раз, когда что-то манипулирует alist или фрагментом alist либо в первом вызове, либо в любом из рекурсивных вызовов.

Изменить: удален вводящий в заблуждение бит