Это правильный способ объяснить псевдокод MergeSort? Какой возврат здесь?

Вы должны помнить, что он выполняет рекурсию вниз по шорт_списку_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, а затем возвращали отсортированный список.