Това ли е правилният начин за обяснение на псевдокода на MergeSort? Какво връщане има тук?

Трябва да запомните, че той рекурсира надолу по short_list_A, докато не получи условието length <= 1, когато се върнете от рекурсивно повикване, той се връща към предишното повикване в стека на извикванията, което изглежда така:

result_A <-- merge_sort(shorter_list_A) 
// *** return here ***
result_B <-- merge_sort(shorter_list_B)
sorted_list <-- merge(result_A, result_B)
return sorted_list

Така че прави същото за result_B, след което обединява резултатите, преди да се върне нагоре в стека на повикванията.

Така че вземаме малък пример, където отстъпът показва дълбочината на рекурсия:

merge_sort([4,7,2,3,1,8,6,5])
    a = merge_sort([4,7,2,3])
        a = merge_sort([4,7])
            a = merge_sort([4])   // Doesn't recurse anymore length <= 1
            b = merge_sort([7])
            r = merge(a,b) = merge([4], [7])
            return r = [4,7]
        b = merge_sort([2,3])
            a = merge_sort([2])
            b = merge_sort([3])
            r = merge(a, b) = merge([2], [3])
            return r = [2,3]
        r = merge(a,b) = merge([4,7], [2,3])
        return r = [2,3,4,7]
    b = merge_sort([1,8,6,5])
        a = merge_sort([1,8])
            a = merge_sort([1])
            b = merge_sort([8])
            r = merge(a, b) = merge([1],[8])
            return r = [1,8]
        b = merge_sort([6,5])
            a = merge_sort([6])
            b = merge_sort([5])
            r = merge(a, b) = merge([6],[5])
            return r = [5,6]
        r = merge(a,b) = merge([1,8], [5,6])
        return r = [1,5,6,8]
    r = merge(a, b) = merge([2,3,4,7], [1,5,6,8])
    return r = [1,2,3,4,5,6,7,8]

Надяваме се, че това помага.

Всяко връщане ще изпрати обратно на повикващия сортиран списък на елементите, които е получил като вход.

На най-долното ниво, когато има само един елемент, списъкът се сортира по подразбиране и се връща. Когато получите два сортирани списъка с по един елемент в result_A и result_B, вие ги предавате и двата на метода merge() и този метод вече върши тежката работа. Това взема двата списъка и ги обединява, за да даде нов списък, който съдържа елементите на двата списъка в сортиран ред.

Как изглежда Merge()?

Merge() ще създаде нов списък. Нека го наречем sorted_list и след това ще започне да чете от head на двата списъка, които е получил като вход и ще вземе минимума от двата елемента на head позиция и ще го постави в sorted_list, който току-що създаде. Методът ще продължи да консумира head от двата входни списъка, докато и двата не бъдат завършени. Сега сливането на двата списъка присъства в sorted_list в сортиран ред. Предположих, че искате списъкът да е сортиран от минимум към максимум.

Преглед на вашия пример

На последното ниво, с единични елементи, първият списък от head -> 8 -> null и вторият списък от head -> 3 -> null ще се слеят, за да образуват head -> 3 -> 8 -> null

На самото това ниво ще обедини двата списъка от head -> 6 -> null и head -> 2 -> null до head -> 2 -> 6 -> null

Нека долното ниво се нарича 0. На ниво 0 имахте само единични елементи. На ниво 1 ще имате списъци от два елемента. На ниво 2 ще имате два списъка от 2 елемента, обединени в един списък.

И така, от head -> 3 -> 8 -> null и head -> 2 -> 6 -> null ще получите head -> 2 -> 3 -> 6 -> 8 -> null.

И накрая този списък ще бъде върнат. Няма повече нива за изкачване. Това е нивото, на което сте получили оригиналния несортиран входен списък, така че при това връщане ефективно ще върнете сортирания списък на повикващия.

За да обобщим

Level num_list Shorter_List_A Shorter_List_B Result_A Result_B sorted_list

2     8,3,6,2  8,3            6,2            3,8      2,6      2,3,6,8

1(a)  8,3      8              3              8        3        3,8  
1(b)  6,2      6              2              6        2        2,6

0(a)  8        -              -              -        -        8
0(b)  3        -              -              -        -        3 
0(c)  6        -              -              -        -        6
0(d)  2        -              -              -        -        2 

И така, започнахме от ниво 2. Извикахме се рекурсивно на ниво 1(a), 1(b). След това от ниво 1 се извикахме рекурсивно отново на ниво 0(a), 0(b), 0(c), 0(d) и след това прехвърлихме обединените резултати до ниво 2 отново и след това върнахме сортиран списък.