title: merge sort/recursion in python
body: <p>I understand how merge sort work but however when I try to implement in python, I think I am still a little confused about how things are really working out on stack. I have a function called merge_sorted_list which is used for merging two sorted list and a function called merge_sort1 and merge_sort2, which are accounted for the recursion process. "merge_sort1" and "merge_sort2" are very similar but only merge_sort2 gave the correct answer. It looks like merge_sort1 was not taking the returned value at each level of the stack. Could anyone tell me what is the difference in the evaluation between merge_sort1 and merge_sort2 please?</p>
  
  <pre><code>def merge_sorted_list(list1,list2):
  
      if(len(list1) == 0 or len(list2) == 0):
          print('input error')
          return;
  
      i = 0
      j = 0
      k = 0
      list_merge = [0]*(len(list1) + len(list2))
      while(i &lt; len(list1) and j &lt; len(list2)):
          if (list1[i] &lt; list2[j]):
              list_merge[k] = list1[i]
              i += 1
          else:
              list_merge[k] = list2[j]
              j += 1
          k += 1
      while(i &lt; len(list1)):
          list_merge[k] = list1[i]
          i += 1
          k += 1
      while (j &lt; len(list2)):
          list_merge[k] = list2[j]
          j += 1
          k += 1
      return(list_merge)
  
  def merge_sort1(mylist):
      print("splitting ",mylist)
      if (len(mylist) &gt; 1):
          mid = len(mylist)//2
          merge_sort1(mylist[:mid])
          merge_sort1(mylist[mid:])
  
      #   lefthalf = mylist[:mid]
      #   righthalf = mylist[mid:]
  
      #   merge_sort1(lefthalf)
      #   merge_sort1(righthalf)
  
          mylist[:] = merge_sorted_list(mylist[:mid],mylist[mid:])
          print("merging result ",mylist)
      return mylist
  
  def merge_sort2(mylist):
      print("splitting ",mylist)
      if (len(mylist) &gt; 1):
  
          mid = len(mylist)//2
  #       merge_sort2(mylist[:mid])
  #       merge_sort2(mylist[mid:])
  
          lefthalf = mylist[:mid]
          righthalf = mylist[mid:]
  
          merge_sort2(lefthalf)
          merge_sort2(righthalf)
  
          mylist[:] = merge_sorted_list(lefthalf,righthalf)
          print("merging result ",mylist)
      return mylist
  </code></pre>
  
  <p>if we try merge_sort1([4,67,3,3,2,6]), the output will be</p>
  
  <pre><code>('splitting ', [4, 67, 3, 3, 2, 6])
  ('splitting ', [4, 67, 3])  
  ('splitting ', [4])
  ('splitting ', [67, 3])
  ('splitting ', [67])
  ('splitting ', [3])
  ('merging result ', [3, 67])
  ('merging result ', [4, 67, 3])
  ('splitting ', [3, 2, 6])
  ('splitting ', [3])
  ('splitting ', [2, 6])
  ('splitting ', [2])
  ('splitting ', [6])
  ('merging result ', [2, 6])
  ('merging result ', [2, 3, 6])
  ('merging result ', [3, 2, 4, 6, 67, 3])
  </code></pre>
  
  <p>The output of merge_sort2([4,67,3,3,2,6]) will be</p>
  
  <pre><code>('splitting ', [4, 67, 3, 3, 2, 6])
  ('splitting ', [4, 67, 3])
  ('splitting ', [4])
  ('splitting ', [67, 3])
  ('splitting ', [67])
  ('splitting ', [3])
  ('merging result ', [3, 67])
  ('merging result ', [3, 4, 67])
  ('splitting ', [3, 2, 6])
  ('splitting ', [3])
  ('splitting ', [2, 6])
  ('splitting ', [2])
  ('splitting ', [6])
  ('merging result ', [2, 6])
  ('merging result ', [2, 3, 6])
  ('merging result ', [2, 3, 3, 4, 6, 67])
  </code></pre>
  
  <p>Thank you very much</p>