gistfile1.txt

def merge_sort(msg, m):
   print msg,m
   result=[]
	#Exit condition

   if len(m) < 2:
      return m

   mid = int(len(m)/2)
   left = m[:mid]
   right = m[mid:]
   #print "left:",left," : right :", right
   
   left = merge_sort("Calling for left", left)

   right = merge_sort("Calling for right", right)
   
   #Merge now
   i = 0
   j = 0

   while i < len(left) and j < len(right):
            print "            LOOP - left:",left," : right :", right
            if left[i] > right[j]:
                result.append(right[j])
                j += 1
            else:
                result.append(left[i])
                i += 1
            print "result: ",result
                
   result += left[i:]
   result += right[j:]
   print "  result: ",result
   return result

if __name__ == "__main__":
	print merge_sort("Main",[9,8,7,6,5,4,3,2,1])
------------------------------------------------------------------------------------------------------------	
Results in the following output:

Main [9, 8, 7, 6, 5, 4, 3, 2, 1]
Calling for left [9, 8, 7, 6]
Calling for left [9, 8]
Calling for left [9]
Calling for right [8]
            LOOP - left: [9]  : right : [8]
result:  [8]
  result:  [8, 9]
Calling for right [7, 6]--------------------------------------> How is this called ?
Calling for left [7]
Calling for right [6]
            LOOP - left: [7]  : right : [6]
result:  [6]
  result:  [6, 7]
            LOOP - left: [8, 9]  : right : [6, 7]----------------------> How is this called ?
result:  [6]
            LOOP - left: [8, 9]  : right : [6, 7]
result:  [6, 7]
  result:  [6, 7, 8, 9]
Calling for right [5, 4, 3, 2, 1]
Calling for left [5, 4]
Calling for left [5]
Calling for right [4]
            LOOP - left: [5]  : right : [4]
result:  [4]
  result:  [4, 5]
Calling for right [3, 2, 1]
Calling for left [3]
Calling for right [2, 1]
Calling for left [2]
Calling for right [1]
            LOOP - left: [2]  : right : [1]
result:  [1]
  result:  [1, 2]
            LOOP - left: [3]  : right : [1, 2]
result:  [1]
            LOOP - left: [3]  : right : [1, 2]
result:  [1, 2]
  result:  [1, 2, 3]
            LOOP - left: [4, 5]  : right : [1, 2, 3]
result:  [1]
            LOOP - left: [4, 5]  : right : [1, 2, 3]
result:  [1, 2]
            LOOP - left: [4, 5]  : right : [1, 2, 3]
result:  [1, 2, 3]
  result:  [1, 2, 3, 4, 5]
            LOOP - left: [6, 7, 8, 9]  : right : [1, 2, 3, 4, 5]
result:  [1]
            LOOP - left: [6, 7, 8, 9]  : right : [1, 2, 3, 4, 5]
result:  [1, 2]
            LOOP - left: [6, 7, 8, 9]  : right : [1, 2, 3, 4, 5]
result:  [1, 2, 3]
            LOOP - left: [6, 7, 8, 9]  : right : [1, 2, 3, 4, 5]
result:  [1, 2, 3, 4]
            LOOP - left: [6, 7, 8, 9]  : right : [1, 2, 3, 4, 5]
result:  [1, 2, 3, 4, 5]
  result:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]