def merge(left,right):
sortedArray=[]
l_idx,r_idx=0,0 #set index for left and right array
#compare values of left and right array
while l_idx<len(left) and r_idx<len(right):
    if(left[l_idx] < right[r_idx]):
        sortedArray.append(left[l_idx])
        l_idx+=1
    else:
        sortedArray.append(right[r_idx])
        r_idx+=1
if l_idx==len(left):
    sortedArray.extend(right[r_idx:])
else:
    sortedArray.extend(left[l_idx:])
return sortedArray

def mergesort(A):
if len(A)<=1:
    return A
middle=len(A)//2
left,right=mergesort(A[:middle]),mergesort(A[middle:])
return merge(left,right)