Why am I getting two different results when merging two sorted lists (Python)
I am confused why I am getting two different outputs when I change the relational operator:
Here is the incorrect version:
listOne = [1,3,6,9,11]
listTwo = [2,4,5,7,8,10,12]
def mergeTwo(l1,l2):
output = []
while l1 and l2:
if l1[0] > l2[0]:
output.append(l2.pop(0))
output.append(l1.pop(0))
if l1:
output.extend(l1)
elif l2:
output.extend(l2)
print output
output:
[1, 2, 3, 4, 6, 5, 9, 7, 11, 8, 10, 12]
but it works when i do this:
listOne = [1,3,6,9,11]
listTwo = [2,4,5,7,8,10,12]
def mergeTwo(l1,l2):
output = []
while l1 and l2:
if l1[0] < l2[0]:
output.append(l1.pop(0))
output.append(l2.pop(0))
if l1:
output.extend(l1)
elif l2:
output.extend(l2)
print output
I change the operator to <and the order of the elements I get out and get this output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
why does the second version merge the two lists correctly, unlike the first?
source to share
Both solutions are actually wrong. The second one just works for your specific input.
They are wrong because you first check if some element is less than the same index element in another list, then you add a smaller element, but then you go and add an element from another list without checking if the next index element is from the first list is less or not.
This is the main reason why the first one does not work. The second one works, only for your specific input -
listOne = [1,3,6,9,11]
listTwo = [2,4,5,7,8,10,12]
Since each element in is listTwo
less than the next element in index in listOne
. Give input where it is not and you will see incorrect results.
The correct way to do it is
def mergeTwo(l1,l2):
output = []
while l1 and l2:
if l1[0] < l2[0]:
output.append(l1.pop(0))
else:
output.append(l2.pop(0))
if l1:
output.extend(l1)
elif l2:
output.extend(l2)
print output
Example / Demo -
>>> listOne = [1,3,6,9,11]
>>> listTwo = [2,4,5,7,8,10,12]
>>>
>>> def mergeTwo(l1,l2):
... output = []
... while l1 and l2:
... if l1[0] < l2[0]:
... output.append(l1.pop(0))
... else:
... output.append(l2.pop(0))
... if l1:
... output.extend(l1)
... elif l2:
... output.extend(l2)
... print(output)
...
>>> mergeTwo(listOne,listTwo)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> listOne = [1,3,6,9,11]
>>> listTwo = [10,15,20,25,30]
>>> mergeTwo(listOne,listTwo)
[1, 3, 6, 9, 10, 11, 15, 20, 25, 30]
source to share
Continue with a while loop. Example:
import os,sys
listOne = [1,3,6,9,11]
listTwo = [2,4,5,7,8,10,12]
def mergeTwo(l1,l2):
output = [];
while l1 and l2:
if l1[0] > l2[0]:
output.append(l2.pop(0))
continue;
output.append(l1.pop(0))
if l1:
output.extend(l1)
elif l2:
output.extend(l2)
print output
mergeTwo(listOne, listTwo);
source to share