gistfile1.txt

def merge_sort(msg, m, depth=0):
   print "  " * depth, 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 (caller: {0})".format(m), left, depth+1)

   right = merge_sort("Calling for right (caller: {0})".format(m), right, depth+1)
   
   #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 (caller: [9, 8, 7, 6, 5, 4, 3, 2, 1]) [9, 8, 7, 6]
     Calling for left (caller: [9, 8, 7, 6]) [9, 8]
       Calling for left (caller: [9, 8]) [9]
       Calling for right (caller: [9, 8]) [8]
            LOOP - left: [9]  : right : [8]
result:  [8]
  result:  [8, 9]
     Calling for right (caller: [9, 8, 7, 6]) [7, 6]
       Calling for left (caller: [7, 6]) [7]
       Calling for right (caller: [7, 6]) [6]
            LOOP - left: [7]  : right : [6]
result:  [6]
  result:  [6, 7]
            LOOP - left: [8, 9]  : right : [6, 7]
result:  [6]
            LOOP - left: [8, 9]  : right : [6, 7]
result:  [6, 7]
  result:  [6, 7, 8, 9]
   Calling for right (caller: [9, 8, 7, 6, 5, 4, 3, 2, 1]) [5, 4, 3, 2, 1]
     Calling for left (caller: [5, 4, 3, 2, 1]) [5, 4]
       Calling for left (caller: [5, 4]) [5]
       Calling for right (caller: [5, 4]) [4]
            LOOP - left: [5]  : right : [4]
result:  [4]
  result:  [4, 5]
     Calling for right (caller: [5, 4, 3, 2, 1]) [3, 2, 1]
       Calling for left (caller: [3, 2, 1]) [3]
       Calling for right (caller: [3, 2, 1]) [2, 1]
         Calling for left (caller: [2, 1]) [2]
         Calling for right (caller: [2, 1]) [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]