Merging sub-arrays of a merge sort-CodePudding

so 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 ff: 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 comparision 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 discared from the stack and right after the left and right sub arrays of [7,1,4,3] are sorted and get discared 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(may be about pointers, in place sorting or how the stack call and releated 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

CodePudding user response：

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?

CodePudding user response：

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.