## TRIAL 1
import math
def MERGE (A,p,q,r):
    steps=0
    n1 = q-p+1
    n2 = r-q
    L = np.array
    R = np.array
    for i in range(1,n1+1):
        L[i] = A[p+i-1]
    for j in range(1,n2+1):
        R[j] = A[q+j]
    steps +=1     #dividing the initial array into 2
    L[n1+1] = math.inf
    R[n2+1] = math.inf
    steps +=1     #adding sentinels
    i=1
    j=1
    for k in range(p,r+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i = i+1
            steps +=1     #placing the smallest number
        else:
            A[k]=R[j]
            j=j+1
            steps +=1
        steps +=k+1 #adding k+1 steps for checking every time the smallest value
    #adding the plot for efficiency
    A_eff[r] = (r,steps) #building an array of "efficiency for each r"
                         #we'll need to multiply by the cost of each step later

    return (A, steps, A_eff[r])

def MERGE_SORT(A,p,r):
    q = (p+r)//2
    steps +=1     #finding the right q
    MERGE_SORT(A,p,q)
    steps +=1     #dividing the initial array into two
    MERGE_SORT(A,q+1,r)
    steps +=1
    MERGE(A,p,q,r)
    steps +=1     #merging the two part of each subsection
return(A,steps)

list = [1,3,4,7,2,10,5,9,8,6]
MERGE_SORT (list,0,9)

##TRIAL 2
import math
def MERGE_SORT (A,p,r):
    steps=0

    q = (p+r)//2
    steps +=1     #finding the right q
    MERGE_SORT(A,p,q)
    steps +=1     #dividing the initial array into two
    MERGE_SORT(A,q+1,r)
    steps +=1
    #MERGE(A,p,q,r)
    #steps +=1

    n1 = q-p+1
    n2 = r-q
    L = np.array
    R = np.array
    for i in range(1,n1+1):
        L[i] = A[p+i-1]
    for j in range(1,n2+1):
        R[j] = A[q+j]
    steps +=1     #dividing the initial array into 2
    L[n1+1] = math.inf
    R[n2+1] = math.inf
    steps +=1     #adding sentinels
    i=1
    j=1
    for k in range(p,r+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i = i+1
            steps +=1     #placing the smallest number
        else:
            A[k]=R[j]
            j=j+1
            steps +=1
        steps +=k+1 #adding k+1 steps for checking every time the smallest value

   #adding the plot for efficiency
    A_eff[r] = (r,steps) #building an array of "efficiency for each r"
                         #we'll need to multiply by the cost of each step later

    return (A, steps, A_eff[r])

list = [1,3,4,7,2,10,5,9,8,6]
MERGE_SORT (list,0,9)
print(list)