merge_two_sorted_arrays.py

def merge_two_arrays_3(a,b): ## len_a=n, len_b=m, m>n
    # n is length of a; m is length of b
    # time O(m+n) space O(n+m)
    from collections import deque # first in first out
    
    da = deque(a)
    db = deque(b)
    
    res = []
    while len(da) or len(db):
        if da and db: 
            xa = da.popleft() # O(1)
            xb = db.popleft() 
            if xa > xb:
                res.append(xb)
                da.appendleft(xa) # O(1)
            else:
                res.append(xa)
                db.appendleft(xb)
            
        elif da and not db:
            xa = da.popleft()
            res.append(xa) # O(1)
        elif db and not da:
            xb = db.popleft()
            res.append(xb)
        
    return res

a = [1,3,4]
b = [2,3,5,6]

print(merge_two_arrays_3(a, b))
# [1, 2, 3, 3, 4, 5, 6]