def merge_sort(L):
    print('merge_sort:', L)
    n = len(L)
    if n <= 1:
        answer = L[:]
    else:
        mid = n // 2
        left, right = L[:mid], L[mid:]
        answer = merge(merge_sort(left), merge_sort(right))
    print('merge_sort:', L, '->', answer)
    return answer


def merge(A, B):
    n = len(A) + len(B)
    C = n * [None]
    a, b = 0, 0
    for c in range(n):
        if a < len(A) and (b == len(B) or A[a] < B[b]):
            C[c] = A[a]
            a = a + 1
        else:
            C[c] = B[b]
            b = b + 1
    return C

def merge_sort_iterative(L):
    Q = [[x] for x in L]
    while len(Q) > 1:
        print("Q = ", Q)
        Q.insert(0, merge(Q.pop(), Q.pop()))
    return Q[0]

from collections import deque

def merge_sort_deque(L):
    Q = deque([[x] for x in L])
    while len(Q) > 1:
        Q.appendleft(merge(Q.pop(), Q.pop()))
    return Q[0]

L = [4,3,8,6,3,1,-5,6,8,-1,9,10] 

print('Merge sort :', merge_sort(L))
print('Iterative  :', merge_sort_iterative(L))
print('Deque      :', merge_sort_deque(L))