AlgorithmFriday_Week5:

merge_sorted_list.py

def merge_sorted_list(a=[],b=[]):
    try:
        if (a == None or len(a)==0) and (b== None or len(b)==0):
            return []
        elif a==None or len(a)==0:
            return b
        elif b==None or len(b)==0:
            return a
        # if last element in a is not greater than first element in b, then append b to a
        elif a[-1]<=b[0]:
            return a+b
        # if last element in b is not greater than first element in a, then append a to b
        elif b[-1]<=a[0]:
            return b+a
        else:
            # check if a and b point to the same location
            if a is b:
                a = a[::]
            # iterate from the end of array b and move a[-1] to its right only if its greater
            for i in range(len(b),0, -1):
                while a and a[-1]>b[i-1]:
                    b.insert(i,a.pop(-1))
            return a+b
    except:
        return []

Thank you for your honest review @meekg33k.

I was just being careful not to create a new array which might cost us some memory, so while I pop from one array, I insert it in the other thus conserving memory.
Although I really don't know much about time and memory complexity, but from what I gathered online,

• The for loop runs n times and the inner loop executes log n times on average which gives O(n log n)
• According to Python wiki Removing elements from the front of a list is O(n), while removing elements from the end is only O(1). But in the case of insert, it is O(n)