Variable's value changing unexpectedly during recursion (MERGE SORT)

Question

Given an input array :

[49, 86, 78]

My code should return:

[[49,1],[78,2],[86,1]]

That is, it should order the array according the first number in each sub array, the second one will be used as an index for later use. I decided to use merge sort for sorting. Here is my code (I know its ugly but please run it once):

def merge_sort(array):
    print("array>>>", array)
    if len(array[:,0]) == 1:
        print('going back')
        return
    arrL = array[0:int(len(array)/2),:]
    arrR = array[int(len(array)/2):,:] 
    print('left>>', arrL, 'right>>', arrR)
    print("*****************")
    print('into left')
    merge_sort(arrL)
    print("*****************")
    print('into right')
    merge_sort(arrR)
    print("*****************")
    print('into MERGE')
    merge(array, arrL, arrR)
    print('going back')

def merge(A, arrL, arrR):
    print("array ", A, "left", arrL, "right", arrR)
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>', arrR)
        if arrR[0,0] < arrL[0,0]:
            print(arrR[0,0], 'is less than', arrL[0,0])
            A[i] = arrR[0]
            arrR = arrR[1:,:]
            print('A>>', A, 'arrR>>', arrR, 'ARRAYLEFT>>', arrL)
        else:
            print(arrL[0,0], 'is less than', arrR[0,0])
            A[i] = arrL[0]
            arrL = arrL[1:,:]
            print('A>>', A, 'arrL>>', arrL)
        i += 1

    print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>>', arrR)

    if len(arrL[:,0]) == 0 :
        print('left exhaused')
        print('A>>', A, 'arrR>>', arrR)
        A[i:,:] = arrR
        print('A>>', A, 'arrR>>', arrR)

    elif len(arrR[:,0]) == 0:
        print('right exhaused')
        print('A>>', A, 'arrL>>', arrL)
        A[i:,:] = arrL
        print('A>>', A, 'arrL>>', arrL)

    print('after merge', A)
    return 

---

import numpy as np
np.random.seed(1)
input_array = [np.random.choice(np.arange(100)) for _ in range(5)]
print(input_array)

outputs:

[37, 12, 72, 9, 75]

then,

new_array = np.array(list( map(list, zip(input_array, [x for x in range(len(input_array)) ])) ))
print(new_array)

outputs:

array([[37,  0],
       [12,  1],
       [72,  2],
       [ 9,  3],
       [75,  4]])

and finally,

merge_sort(new_array)

gives the following (I have added only the part of interest). Notice how once we go into MERGE the value of arrL changes to the value of arrR once arrR becomes [] marked in the code by <<<=== sign:

array>>> [[37  0]
 [12  1]
 [72  2]
 [ 9  3]
 [75  4]]
left>> [[37  0]
 [12  1]] right>> [[72  2]
 [ 9  3]
 [75  4]]
*****************
into left
array>>> [[37  0]
 [12  1]]
left>> [[37  0]] right>> [[12  1]]
*****************
into left
array>>> [[37  0]]
going back
*****************
into right
array>>> [[12  1]]
going back
*****************
into MERGE
array  [[37  0]
 [12  1]] left [[37  0]] right [[12  1]]
ARRAYLEFT>> [[37  0]] ARRAYRIGHT>> [[12  1]]  <<<=== # arrL = [[37  0]]
12 is less than 37
A>> [[12  1]
 [12  1]] arrR>> [] ARRAYLEFT>> [[12  1]]
ARRAYLEFT>> [[12  1]] ARRAYRIGHT>> []       <<<=== # arrL = [[12  1]]
right exhaused
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
after merge [[12  1]
 [12  1]]
going back
*****************
## .... and so one....

This error seems to occur whenever the code goes into MERGE and arrR = [] so after this

print(new_array)

outputs:

array([[ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [75,  4]])

which is clearly the wrong answer. Please help me understand where I am making a mistake... I have been staring at the code and the output for a good 20 minutes now but can't seem to find it. Any suggestion/criticism would be highly appreciated.

Answer 1

That's kinda hard to understand, mainly due to similar print messages in different places. The issue seems to be connected with the fact that A[0] and arrL are the same arrays. That would not be the case with plain python lists, but numpy seems to do some sort of optimization to save memory. So when you modify A[i] = arrR[0], you basically assign arrL = arrR. Besides that, the implementation seems to be pretty unusual for the merge sort algorithm. You need neither NumPy nor 2d array, just a list of numbers is what you want to sort. If you just want a sorted list, you can use the built-in implementation, sorted(array). Finally, I would kindly recommend getting used to the debugger (one in your IDE, or PDB https://realpython.com/python-debugging-pdb/ ) instead of print statements, it is a much more effective way to understand what the code is doing. It may be hard at first, but trust me, it will pay off and help you to progress as a developer. Stay safe.

Answer 2

Adding .copy() everywhere solved my problem.

def merge(A,arrL,arrR):
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        if arrR[0,0] < arrL[0,0]:
            A[i] = arrR[0].copy()
            arrR = arrR[1:,:].copy()
        else:
            A[i] = arrL[0].copy()
            arrL = arrL[1:,:].copy()
        i+=1

    if len(arrL[:,0]) == 0 :
        A[i:,:] = arrR.copy()

    elif len(arrR[:,0]) == 0:
        A[i:,:] = arrL.copy()

    return 

def merge_sort(array):
    if len(array[:,0]) == 1:
        return
    arrL = array[0:int(len(array)/2),:].copy()
    arrR = array[int(len(array)/2):,:] .copy()
    merge_sort(arrL)
    merge_sort(arrR)
    merge(array,arrL,arrR)