Реализация на Mergesort в 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]

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

Следователно актуализацията на вашия списък се случва всеки път, когато нещо манипулира alist или част от alist, или в първото извикване, или в някое от рекурсивните извиквания.

Редактиране: премахнат подвеждащ бит