Merging sub-arrays of a merge sort

Question

I found the following code from geeks for geeks and I don't seem to understand how the sub-arrays are being sorted(i.e. when we sort the left sub-array and then the right sub-array and then, merge both left and right sub-arrays, how come we don't get a wrong answer as the elements sorted in the sub-array merging is the sub-arrays themselves, which according to my understanding are being initialized all the time in the ff code). To better explain my question, I am using an example as following: input_array = [7,1,4,3,5,2,9,8] when we recursively call mergesort, m(7,1,4,3]->m[7,1]->m[7]->m[1]->sort[7,1]-> then we get it sorted to [1,7] and then we proceed to the right half, m[4,3]->m[4]->m[3]->sort[4,3]-> then we get it sorted to [3,4]. what I don't understand is that when we try to sort [7,1,4,3], as we can see in the code below the comparison is made between all the left sub-arrays and all the right sub-arrays and when we do that, the left and right sub-arrays aren't sorted(i am sure I am wrong but in my understanding, the sorted sub-arrays above are already forgotten and discarded from the stack and right after the left and right sub-arrays of [7,1,4,3] are sorted and get discarded the top of the stack is now m[7,1,4,3] and its L is still [7,1] and its R is [4,3] as they weren't updated in the previous sub-array sorting call). I am sure I am missing something here(maybe about pointers, in-place sorting, or how the stack call and related stuff works but I still can't see why?) I have included the code below

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

MoonMist · Answer 1 · 2022-09-05T09:23:43.193

By the looks of it, your difficulty in understanding this is like you said, to do with pointers, or at least passing variables through functions in python.

Lets say we have a function like this:

def foo(my_param):

and we call it with foo(my_variable)

Python does what is called "passing by assignment" which, for simplicity, basically runs this expression: my_param = my_variable. If we were to run my_new_list = my_old_list in python, the old list is not copied, but instead its instance address is copied to my_new_list, which means a list in python is passed by its address and not its value, so the list changes hands for the new function to handle it. In the previous example, if my_variable was a list object, then any changes to my_param, for example my_param[0] = 2 will change my_variable as well.

In your example code, the param is arr and you can see that its values are being modified within the function, which means whichever part of the stack called this function is having its passed variable modified as well.

You might find this post about passing variables in python helps: How do I pass a variable by reference?

score 0 · Answer 2 · answered Sep 05 '22 at 07:25

It's why mergesort is called recursively.

Array with just one element is obviously sorted. Now if we have n elements, we do not only merge arrays, we first call mergesort for that smaller arrays. Again, if smaller arrays has more than 1 element, we call mergesort on them before we go to merge parts.

So generally mergesort function is called lg_n times.

score 0 · Answer 3 · answered Sep 05 '22 at 20:17

The initial call makes a copy of left and right half of arr into L and R. Then it calls itself to sort L, which makes a copy of the caller's L into a callee's L and R, and continues doing this until it produces two sub-arrays of size 1, and only then does it reach the merge step to merge the callee's L and R into the caller's array. After that, it follows the call chain up and down depth first, left first until it reaches the initial call, where the first and now sorted instances of L and R are merged back into the original arr.

The order is depth first left first:

[7   1   4   3   5   2   9   8]
[7   1   4   3] [5   2   9  8]
[7   1] [4   3]
[7] [1]
[1   7]
        [4] [3]
        [3   4]
[1   3   4   7]
                [5   2] [9   8]
                [5] [2]
                [2   5]
                        [9] [8]
                        [8   9]
                [2   5   8   9]
[1   2   3   4   5   7   8   9]

Note that top down merge sort is mostly academic. Most actual libraries for a stable sort use a hybrid of insertion sort and bottom up merge sort, such as Tim sort.

Merging sub-arrays of a merge sort

3 Answers3