What is the problem with this merge sort algorithm?

Question

I'm trying to implement the python code for Merge Sort Algorithm using recursive functions in python. But the code is not working as expected. The value of q in the code is not decreasing as expected of it and is stuck on the 1st value and the function is falling into an infinite recursive function.

def merge(A,p,q,r):
    """ This function merges 2 sorted subarrays A[p .. q] and A[q+1 .. r] into a single sorted array A[p .. r]"""
    A1 = A[p:q]
    A2 = A[q:r]
    A1 = A1 + [max(A)+1]
    A2 = A2 + [max(A)+1]
    #print(A1,A2)
    i, j = 0,0
    for k in range(p,r):
        if(A1[i]<=A2[j]):
            A[k] = A1[i]
            i+=1
        else:
            A[k] = A2[j]
            j+=1
        #print(i,j,k)
        #print(A)
    return A

def mrgSort(A,p,r):
    r=len(A)
    if(p<(r-1)):
        q = (p+r)//2
        print(q)
        A1 = mrgSort(A,p,q)
        #print(A)
        A2 = mrgSort(A,q,r)
        #print(A)
        A = [A1,A2]
        merge(A,p,q,r)
        #print(A)  
    return A


print(mrgSort([0,3,2,-1,9,5,6,2,1],0,9))
#print(merge([0,3,5,10,-1,1,5,7,9],0,4,9))

Answer 1

def merge(A,p,q,r):
    """ This function merges 2 sorted subarrays A[p .. q] and A[q+1 .. r] into a single sorted array A[p .. r]"""
    A1 = A[p:q]
    A2 = A[    q:r]

    A1 = A1 + [(max(A)+1)]
    A2 = A2 + [(max(A)+1)]
    i, j = 0,0
    for k in range(p,r):
         if A1[i]<=A2[j]:
            A[k] = A1[i]
            i+=1
        else:
            A[k] = A2[j]
            j+=1
return A

def mrgSort(A,p,r):
    if(p<(r-1)):
        q = (p+r)//2
        A = mrgSort(A,p,q)
        A = mrgSort(A,q,r)
        A = merge(A,p,q,r)
    return A

Some mistakes you make:

• Doing r=len(A) resets your variable r every time.

• A = [A1,A2] gives you a list of lists. If you want to concatenate lists, do: A = A1 + A2

• Your use of concatenating A1 en A2 was wrong when you look at the way you implemented the algorithm.