def merge(A,B):
    # assume A, B sorted
    # return X := combination of A and B, sorted
    i = 0                       # index into A
    j = 0                       # index into B
    X = []
    while i < len(A) or j < len(B):
        # find the minimum between A[i] (if it exists) and
        # B[j] (if it exists)
        # Two cases:
        #   1) we append A[i], then i = i + 1
        #   2) we append B[j], then j = j + 1
        if i < len(A) and (j >= len(B) or A[i] <= B[j]):
            X.append(A[i])
            i = i + 1
        else:
            X.append(B[j])
            j = j + 1
    return X

def merge_sort(A, begin, end):
    # begin is the first index of the range of A we want to merge-sorted
    # end is the one-past-last index of the range of A we want to merge-sorted
    # Example: A = [1, 2, 3, 4, 5, 6, 7, 8] 
    #          begin=0                     end=8
    if end - begin == 1:
        return [ A[begin] ]
    elif end - begin == 0:
        return []

    m = (begin + end) // 2
    # Example: A = [1, 2, 3, 4, 5, 6, 7, 8] 
    #          begin=0         m=4         end=8
    L = merge_sort(A, begin, m) # excludes position m
    R = merge_sort(A, m, end)   # excludes position end
    return merge(L,R)