Why do I get two different Outputs, when merging two sorted lists (Python)

Question

I am confused as to why i get 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

the output is: [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 elements I pop off and I 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?

Answer 1

Both solutions are actually wrong. The second one just happens to work for your particular input.

They are wrong, because you first check if a certain element is smaller than the same index element in other list, then you add the smaller element, but then you go and add the element from the other list as well, without checking whether the next index element from first list is smaller or not.

This is the main reason why the first one does not work. The second one works, only for your particular input -

listOne = [1,3,6,9,11]
listTwo = [2,4,5,7,8,10,12]

Because each element in listTwo is smaller than the next index element in listOne . Give an input where this is not the case and you would see the wrong results.

Correct way to do it -

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]