Python: Inplace Merge sort implementation issue

Question

I am implementing inplace merge sort algorithm in python3. Code takes an input array and calls it self recursively (with split array as input) if length of the input array is more than one. After that, it joins two sorted arrays. Here is the code

def merge_sort(array):

    """
    Input : list of values
    Note :
        It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
    Returns : sorted list of values

    """

    def join_sorted_arrays(array1, array2):

        """
        Input : 2 sorted arrays.
        Returns : New sorted array

        """

        new_array = []    # this array will contain values from both input arrays.
        j = 0             # Index to keep track where we have reached in second array
        n2 = len(array2)

        for i, element in enumerate(array1):
            # We will compare current element in array1 to current element in array2, if element in array2 is smaller, append it
            # to new array and look at next element in array2. Keep doing this until either array2 is exhausted or an element of
            # array2 greater than current element of array1 is found.
            while j < n2 and element > array2[j]:
                new_array.append(array2[j])
                j += 1
            new_array.append(element)
        # If there are any remaining values in array2, that are bigger than last element in array1, then append those to 
        # new array.
        for i in range(j,n2):
            new_array.append(array2[i])
        return new_array

    n = len(array)
    if n == 1:
        return array
    else:
        # print('array1 = {0}, array2 = {1}'.format(array[:int(n/2)], array[int(n/2):]))
        array[:int(n/2)] = merge_sort(array[:int(n/2)])
        array[int(n/2):] = merge_sort(array[int(n/2):])
        # print('array before joining : ',array)
        array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):])
        # print('array after joining : ',array)
        return array

Now if the code is tested,

 a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4]
 merge_sort(a)
 print(a)
 out : [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10]

If you uncomment the print statements in the above function, you will notice that, a = given output, just before the last call of join_sorted_arrays. After this function has been called, array 'a' should be sorted. To my surprise, if I do the following, output is correct.

a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4]
a = merge_sort(a)
print(a)
out : [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10]

I need some help to understand why this is happening. I am beginner, so any other comments about coding practices etc. are also welcome.

Answer 1

When you reassign array as the output of join_sorted_arrays() with

array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):])

you're not updating the value of a anymore.

Seeing as you pass in a as the argument array, it's understandable why all variables named array in a function might seem like they should update the original value of array (aka a). But instead, what's happening with array = join_sorted_arrays(...) is that you have a new variable array scoped within the merge_sort() function. Returning array from the function returns that new, sorted, set of values.

The reference to a was being modified up until that last statement, which is why it looks different with print(a) after merge_sort(a). But you'll only get the final, sorted output from the returned value of merge_sort().

It might be clearer if you look at:

b = merge_sort(a)
print(a) # [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10]
print(b) # [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10]

Note that Python isn't a pass-by-reference language, and the details of what it actually is can be a little weird to suss out at first. I'm always going back to read on how it works when I get tripped up. There are plenty of SO posts on the topic, which may be of some use to you here.
For example, this one and this one.