if statement is misbehaving for some inputs

Question

I am trying to implement MergeSort in python. But for some reason, I am getting unexpected behaviour and I would appreciate if second pair of eyes can have a look and identify what I might be doing wrong. The code looks like following:

# Implementation of Merge-Sort algorithm using Divide and Conquer paradigm

# Reading the unsorted array from a file into a list
#filename = 'test.txt'
#
#array = [line.rstrip('\n') for line in open(filename)]
#
#print(array)
array = ['1', '3', '5', '7', '4', '6', '8', '2', '19', '15', '12', '11', '16', '17', '10', '20'] 

#function for dividing and calling merge function
def Mergesort(array):
  n = len(array)
  if(n<2):
    return

  mid = n/2
  left = []
  right = []

  for i in range(mid):
    number = array[i]
    left.append(number)  

  for i in range(mid,n):
    number = array[i]
    right.append(number)

  Mergesort(left)
  Mergesort(right)

  Merge(left,right,array)

def Merge(left, right, array):
    i = 0
    j = 0
    #k = 0

    print'Merging!'
    print(array)
    print(left)
    print(right)


    for k in range(len(array)):
        if (i<len(left) and j<len(right)):
          print('value of i is ',i, 'value of j is', j)
          print('Entering first while statement')
          if(left[i] < right[j]):
            print('Left index value is ', left[i], 'Right index value is ', right[j])
            array[k] = left[i]
            print('Value is being entered at index ', k, 'and the value is', array[k])
            print('End of iteration ', i, j)
            i = i+1
          else:
            print('Entering the else of first while statement')
            print('Left index value is ', left[i], 'Right index value is ', right[j])
            array[k] = right[j]
            print('Value is being entered at index ', k, 'and the value is', array[k])
            print('End of iteration ', i, j)
            j = j+1
      elif(i<len(left)):
        print('Entering second while statement')
        print('Left index value is ', left[i])
        array[k] = left[i]
        print('Value is being entered at index ', k, 'and the value is', array[k])
        i = i+1
      else:
        print('Entering third while statement')
        print('Right index value is ', right[j])
        array[k] = right[j]
        print('Value is being entered at index ', k, 'and the value is', array[k])
        j = j+1
      print('Merging done! Sorted array is ',array)

#calling Mergesort
Mergesort(array)
for i in array:
  print i,

P.S: There are a lot of print statements for debugging. I have left them here so that it is possible to see where exactly I am looking for the respective values in the execution flow

Now, upon running the above program I get the expected behaviour for a few sets of arrays, like:

Merging!
['1', '3']
['1']
['3']
('value of i is ', 0, 'value of j is', 0)
Entering first while statement
('Left index value is ', '1', 'Right index value is ', '3')
('Value is being entered at index ', 0, 'and the value is', '1')
('End of iteration ', 0, 0)
Entering third while statement
('Right index value is ', '3')
('Value is being entered at index ', 1, 'and the value is', '3')  
('Merging done! Sorted array is ', ['1', '3'])
Merging!  
['5', '7']
['5']
['7']
('value of i is ', 0, 'value of j is', 0)  
Entering first while statement
('Left index value is ', '5', 'Right index value is ', '7')
('Value is being entered at index ', 0, 'and the value is', '5')
('End of iteration ', 0, 0)
Entering third while statement
('Right index value is ', '7')
('Value is being entered at index ', 1, 'and the value is', '7')
('Merging done! Sorted array is ', ['5', '7'])
Merging!
['1', '3', '5', '7']
['1', '3']
['5', '7']
('value of i is ', 0, 'value of j is', 0)
Entering first while statement
('Left index value is ', '1', 'Right index value is ', '5')
('Value is being entered at index ', 0, 'and the value is', '1')
('End of iteration ', 0, 0)
('value of i is ', 1, 'value of j is', 0)
Entering first while statement
('Left index value is ', '3', 'Right index value is ', '5')
('Value is being entered at index ', 1, 'and the value is', '3')
('End of iteration ', 1, 0)
Entering third while statement
('Right index value is ', '5')
('Value is being entered at index ', 2, 'and the value is', '5')
Entering third while statement
('Right index value is ', '7')
('Value is being entered at index ', 3, 'and the value is', '7')
('Merging done! Sorted array is ', ['1', '3', '5', '7'])

Whereas, in the later stages of execution the behaviour of the if is not as desired:

Merging!
['1', '3', '5', '7', '4', '6', '8', '2', '19', '15', '12', '11', '16', '17', '10', '20']
['1', '2', '3', '4', '5', '6', '7', '8']
['10', '11', '12', '15', '16', '17', '19', '20']
('value of i is ', 0, 'value of j is', 0)
Entering first while statement
('Left index value is ', '1', 'Right index value is ', '10')
('Value is being entered at index ', 0, 'and the value is', '1')
('End of iteration ', 0, 0)
('value of i is ', 1, 'value of j is', 0)
Entering first while statement
Entering the else of first while statement
('Left index value is ', '2', 'Right index value is ', '10')
('Value is being entered at index ', 1, 'and the value is', '10')
('End of iteration ', 1, 0)
('value of i is ', 1, 'value of j is', 1)
Entering first while statement
Entering the else of first while statement
('Left index value is ', '2', 'Right index value is ', '11')
('Value is being entered at index ', 2, 'and the value is', '11')
('End of iteration ', 1, 1)
('value of i is ', 1, 'value of j is', 2)

I am not able to understand that why is this happening. By the looks of it, it seems like I am missing out on something pretty obvious, but have not been able to figure it out yet.

I would appreciate if you can give your thoughts on it.

Answer 1

The problem is that you aren't sorting lists of numbers, you are sorting lists of strings. If you do a string comparison, '10' comes before '2' in alphabetical order.

All you need to do is define your lists using numbers.

Change

array = ['1', '3', '5', '7', '4', '6', '8', '2', '19', '15', '12', '11', '16', '17', '10', '20'] 

to

array = [1, 3, 5, 7, 4, 6, 8, 2, 19, 15, 12, 11, 16, 17, 10, 20]