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 []

Hello @Julisam, thank you for participating in Week 5 of #AlgorithmFridays.

This is a really clean solution. I like the robust checks you have on lines 3 - 8 and the extra optimization on lines 10 - 13. Really sweet!

I thought to share some feedback with you:

• On lines 20 - 23, you have a while loop nested in a for loop. What do you think is the time complexity of that? Is there a more time-efficient way we could solve that?

• Also on line 22 specifically, there is an insert operation to insert at position i and a pop operation that removes the last element from array a. How expensive do you think these operations are, especially considering that you use them in a nested loop? Do you think that they impact on the efficiency of your solution? Do let me know what you think.

But really nice job! Kudos to you!

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)