#------------------------TDdivideandconquer2------------------------#


#####################[Code 1]##########################

def merge(A, B):
    C = []
    a, b = 0, 0
    for i in range(0, len(A)+len(B)):
        if (b == len(B)) or (a < len(A) and A[a] <= B[b]):
            C.append(A[a])
            a += 1
        elif (a == len(A)) or (b < len(B) and B[b] <= A[a]):
            C.append(B[b])
            b += 1
    return C
    
print( merge( [1,4,30], [0,3,10,20,50] ) )



#####################[Code 2]##########################

def merge(A, B):
    C = []
    a, b = 0, 0
    for i in range(0, len(A)+len(B)):
        if (b == len(B)) or (a < len(A) and A[a] <= B[b]):
            C.append(A[a])
            a += 1
        elif (a == len(A)) or (b < len(B) and B[b] <= A[a]):
            C.append(B[b])
            b += 1
    return C

def mergeSort_recursive(A):
    if len(A) == 1: return list(A)

    m = len(A) // 2
    G = mergeSort_recursive(A[:m])
    D = mergeSort_recursive(A[m:])
    return merge(G, D)
    
print( mergeSort_recursive([4,1,66,23,131,6]) )



#####################[Code 3]##########################

def merge(A, B):
    C = []
    a, b = 0, 0
    for i in range(0, len(A)+len(B)):
        if (b == len(B)) or (a < len(A) and A[a] <= B[b]):
            C.append(A[a])
            a += 1
        elif (a == len(A)) or (b < len(B) and B[b] <= A[a]):
            C.append(B[b])
            b += 1
    return C

def mergeSort(A):
    s = 1
    while s < len(A):
        i = 0
        while (i < len(A)):
            A[i:i+2*s] = merge(A[i:i+s], A[i+s:i+2*s])
            i += 2*s
        s = 2*s

B = [9, 1, 53, 81, 16, 51, 12, 9]
mergeSort(B)
print(B)



#####################[Code 4]##########################

def quickSort_recursive(A):
    if len(A) <= 1:
        return list(A)

    pivot = A[0]

    M = [ v for v in A if v == pivot ]
    G_input = [ v for v in A if v < pivot ]
    D_input = [ v for v in A if v > pivot ]

    G_output = quickSort_recursive(G_input)
    D_output = quickSort_recursive(D_input)

    return G_output + M + D_output



#####################[Code 5]##########################

def findBestStrategy_slow(i, j): #i, i+1, ..., j
    if i == j:
        return (i, 0)

    c1 = i + findBestStrategy_slow(i+1, j)[1]
    c2 = j + findBestStrategy_slow(i, j-1)[1]

    if c1 < c2:
        best_choice, best_choice_cost = i, c1
    else:
        best_choice, best_choice_cost = j, c2

    for k in range(i+1, j):
        l = findBestStrategy_slow(i, k-1)[1]
        r = findBestStrategy_slow(k+1, j)[1]

        c = k + max(l, r)
        if c < best_choice_cost:
            best_choice_cost = c
            best_choice = k

    return (best_choice, best_choice_cost)

print(findBestStrategy_slow(1,3))