# An alternative to Solution 1 for Merge Two Sorted Lists

I believe this solution would be easier to understand than the current one proposed in Solution1. It does have the same space and time complexity as it is using a new list to hold the sorted elements from both lists.

``````def merge_list_additional_list(lst1, lst2):
"""
Two pointer solution. We start the head of each list and continue until either one or both lists are exhausted.
Append the rest of the list to the merged list. O(m * n) if any of the list have a different length,
otherwise O(n^2) time and O(n + m) space
:param lst1:
:param lst2:
:return:
"""
i, j = 0, 0

merged_list = []

while i < len(lst1) and j < len(lst2):
if lst1[i] > lst2[j]:
merged_list.append(lst2[j])
j += 1
else:
merged_list.append(lst1[i])
i += 1

if i < len(lst1):
merged_list += lst1[i:]

if j < len(lst2):
merged_list += lst2[j:]

return merged_list``````
2 Likes

Thank you @Dragos1. This is a good solution.
educative.io

In this course section on merging two sorted lists. Isnâ€™t this just as a efficient

``````def mergeList(list1, list2):
n1,n2 = len(list1), len(list2)
if n2> n1:
list2.extend(list1) # O(n1)
list2.sort() # O((n1 + n2) Log (n1 + n2))  = O(n Log n)
return list2
else:
list1.extend(list2) # O(n2)
list1.sort() # O((n1 + n2) Log (n1 + n2)) = O(n Log n)
return list1
``````

Which if n1 == n2 == n we have as O(n)

2 Likes

Wow, thatâ€™s great @Oti_Rowland.
Happy Learning at Educative
Educative.io

1 Like

@Dragos1 nice solution. You can also remove the last two if statements by adding one extra condition in the first if statement.

``````def merge_lists(lst1, lst2):
i, j = 0, 0
result = []
while i < len(lst1) and j < len(lst2) :
if i < len(lst1) and lst1[i] < lst2[j]:
result.append(lst1[i])
i += 1
else:
result.append(lst2[j])
j += 1
return result
``````

@Anum_Hassan

``````    def merge_lists(lst1, lst2):
lst1.extend(lst2)
lst1.sort()
return lst1``````

Does this valid?
def merge_lists(lst1,lst2):
return sorted(lst1+lst2)

Based on the posted solution it is unclear to me how a comparison is handled when the elements have the same value. For instance list1 = [0, 2, 4, 6] and list2 = [0, 10, 11, 12]. If comparing list1[0] < list2[0], youâ€™re checking if 0 is less than 0, so how is this handled in the proposed solution?

Hereâ€™s my answer. It passed all the tests, although I am sure it is not optimal:

``````def merge_lists(lst1, lst2):
new_list = lst1 + lst2
length = len(new_list)
counter = 0
while counter < length-1:
if new_list[counter] > new_list[counter + 1]:
new_item = new_list[counter + 1]
new_list.pop(counter + 1)
new_list.insert(counter, new_item)
counter = 0
else:
counter = counter + 1
return new_list
``````

had the same solution, and is it just me or it seems that suggested Solution 1 has kind of unnecessary overthinking with that 3rd list with placeholders? Why do you need to create a full list before, if you can just fill it on the go?

And also a remark about that comment by OP:

Why so? Time complexity is not O(n^2), we are traversing every array for one time only, itâ€™s just O(M+N), or am I missing something?

fixed: wrote O(M*N) my mistake the 1st time, meant O(M+N)

You are correct itâ€™s O(m*n) there is a single pass, however if m=n would that not be n2?

ah, haha, I actually made a mistake in that comment, I meant the complexity should be O(m + n) not O(m * n), no? We are going through each list just once, we are not going through each list several times depending on the size of another list, as it would be in some kind of â€śfor loop inside of for loopâ€ť.

Even in the official solution itâ€™s written that â€śThe time complexity for this algorithm is O(n+m), where n and m are the lengths of the lists.â€ť