title: Merge Sort Implementation Check
body: <p>I am doubtful of my implementation of the merge sort for two cases specifically:
  <br>
  <br>
  1. If the size of the list is 2, then I have swapped the values if they are not in the ascending order else I have returned them.
  <br>
  <br>
  2. In the merge function when the list tries to check outside the number of elements in it, I have assigned the greatest number (<code>9999</code>), so that in case of comparison with it always comes false.
  <br>
  Can anyone tell me if the implementation of my merge sort is correct or not? As in sorting is complete, but is the implementation of merge sort exact or is it wrong because of the cases?
  <br>
  <br>
  Here is my code:
  <br></p>
  
  <pre><code># unsorted LIST
  u_list = [3, 6, 8, 1, 4, 7, 2, 12, 45];
  
  # Size of the unsorted list
  global_size = len(u_list)
  
  def foo(temp_list):
      size_of_list = len(temp_list)
      # If the size of the list is 1
      if size_of_list == 1:
          return temp_list
  
      # If the size of the list is 2
      if size_of_list == 2:
          if temp_list[0] &gt; temp_list[1]:
              temp_list[0],temp_list[1] = temp_list[1],temp_list[0]
              return temp_list
          else: 
              return temp_list
  
      # If the size of the list is greater than 2                
      if size_of_list &gt; 2:
          count = 1
          i = 0
          if size_of_list % 2 == 0:
              mid1 = size_of_list / 2
          else:
              mid1 = (size_of_list / 2) + 1
  
          mid2 = size_of_list - mid1
  
          newlist1 = list()
          newlist2 = list()
  
          for e in temp_list:
              if count &gt;= mid1 + 1:
                  newlist2.append(e)
              else:
                  newlist1.append(e)
              if count == size_of_list:
                  break
              count = count + 1
          sorted_list = list()
          return merge(foo(newlist1), foo(newlist2))
  
  # Merging all the sorted components
  def merge(list1, list2):
      i = 0
      j = 0
      k = 0
      size_of_list = len(list1) + len(list2)
      sorted_list = list()
      while k &lt;= size_of_list - 1:
          if i == len(list1):
              list1.append(9999)
          if j == len(list2):
              list2.append(9999)
  
          if list1[i] &lt; list2[j]:
              sorted_list.append(list1[i])
              i = i + 1
          elif list2[j] &lt; list1[i]:
              sorted_list.append(list2[j])
              j = j + 1
          k = k + 1
      return sorted_list
  
  print foo(u_list)
  </code></pre>