Is this the right way to explain MergeSort pseudocode? What return does here?

Question

On different websites the pseudocode is similar to this one below:

merge_sort(num_list)
length <-- length of num_list

if length > 1

    shorter_list_A <-- first half of num_list
    shorter_list_B <-- second half of num_list

    result_A <-- merge_sort(shorter_list_A)
    result_B <-- merge_sort(shorter_list_B)

    sorted_list <-- merge(result_A, result_B)

    return sorted_list
else
    return num_list
end

So if we have 4 numbers: 8,3,6,2

MergeSort(8,3,6,2)

first half of the numbers put to Shorter_list_A(8,3) and second half of the numbers put to Shorter_list_B(6,2)

    shorter_list_A <-- first half of num_list
    shorter_list_B <-- second half of num_list

So we have now two lists: shorter_list_A(8,3) and Shorter_list_B (6,2)

    result_A <-- merge_sort(shorter_list_A)

Merge_sort calls merge_sort again, so what happens there is this:

merge_sort(Shorter_list_A)  // also 8,3
length <-- length of Shorter_list_A

if length > 1

    shorter_list_A <-- first half of Shorter_list_A 
//8 put to Shorter_list_A
    shorter_list_B <-- second half of Shorter_list_A
//3 put to Shorter_list_B

    result_A <-- merge_sort(shorter_list_A)
//merge_sort calls merge_sort again
    result_B <-- merge_sort(shorter_list_B)

    sorted_list <-- merge(result_A, result_B)

    return sorted_list
else
    return Shorter_list_A
end

So we have now two lists again: shorter_list_A(8) and Shorter_list_B (6)

From the explanation so far, have I understood that right or complete wrong?

Then it calls merge_sort again. Since lenght of Shorter_list_A is only 1, it contains only one number which is 8. S what happens there is this:

merge_sort(Shorter_list_A)
length <-- length of Shorter_list_A
    return Shorter_list_A
end

It returns Shorter_list_A, which is 8.

What return does exacly here? I'm stuck in there.

Answer 1

You have to remember that it recurses down short_list_A until it gets the condition length <= 1 when you return from a recursive call it returns to the previous call in the call stack, which looks like:

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

So it does the same for result_B then merges the results before returning up the call stack.

So taking a small example, where indentation shows the recursion depth:

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]

Hopefully that helps.