

def mergesort_recursive(A):
    mergesort_helper(A, 0, len(A))


def mergesort_iterative(A):
    n = len(A)
    i = 1
    while i < n:
        j = 0
        while j < n:
            left = j
            mid = j+i
            right = min(j+i+i, n) # len(A) ist nicht immer Zweierpotenz
            print(left, mid, right)
            merge(A, left, mid, right)
            j = j + 2*i
        i = 2*i



def mergesort_helper(A, left, right):
    # Achtung: "right" ist eigentlich "right+1", damit
    # in den Schleifen das '+1' weggelassen werden kann
    if left < right-1: 
        mid = (left + right) // 2
        print('divide:', A[left:mid], '+', A[mid:right])
        print(50*'-')
        mergesort_helper(A, left, mid)
        mergesort_helper(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    L = A[left:mid] + [float('inf')]
    R = A[mid:right] + [float('inf')]
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j+1
    print('merge:', A[left:right])
    print(50*'-')
        

    

    
