If we allow O(m) extra space complexity then we can solve this in O(m+n) which is far better than Solution 2:
def merge_lists(lst1, lst2):
"""
Extend the longer list and start from the end of the two lists.
In each iteration find the largest number between them and add that
at the end of the extended list.
"""
i, j = len(lst1) - 1, len(lst2) - 1
if len(lst1) >= len(lst2):
result = lst1
result.extend(lst2)
else:
result = lst2
result.extend(lst1)
k = len(result) - 1
while i >= 0 and j >= 0:
if lst1[i] >= lst2[j]:
result[k] = lst1[i]
i -= 1
else:
result[k] = lst2[j]
j -= 1
k -= 1
while i >= 0:
result[k] = lst1[i]
i -= 1
k -= 1
while j >= 0:
result[k] = lst2[j]
j -= 1
k -= 1
return result
In case we want to go further and solve the question in O(1) extra space complexity, then we can modify heap sort such that it treats the two separate lists as one list and run sorting in-place so we get extra space complexity of O(1) and time complexity of O((m+n)*log(m+n)). Here, result is just a “fake” list that retrieves the items from lst1 or lst2 based on the index:
def getitem(i):
if i < len(lst1):
return lst1[i]
else:
return lst2[len(lst1) - i]
def setitem(i, val):
if i < len(lst1):
lst1[i] = val
else:
lst2[len(lst1) - i] = val