problem3.py

# Just sending around another array with the indexes
# and transforming it in the samw ways as the input

def mergesort(A,P):
    n = len(A)
    if n == 1:
        return A,P
    A1,P1 = mergesort(A[0:n//2],P[0:n//2])
    A2,P2 = mergesort(A[(n//2):],P[(n//2):])
    return merge(A1,A2,P1,P2)

def merge(A1,A2,P1,P2):
    B = []
    P = []
    while len(A1) > 0 and len(A2) > 0:
        if A1[0] > A2[0]:
            B.append(A2.pop(0))
            P.append(P2.pop(0))
        else:
            B.append(A1.pop(0))
            P.append(P1.pop(0))
    B += A1
    B += A2
    P += P1
    P += P2
    return B,P

def mergehelp(A):
    return mergesort(A,list(range(len(A)))) # list(range(len(A))) generates an array with elements from 0 up to N-1

print(mergehelp([7, 5, 2, 4, 3, 9]))