title: Analysing merge sort complexity
body: <p>The code I wrote is as follows:</p>
  
  <pre><code>def merge(A, B): #merging two sorted lists
     index_a = index_b = 0
     result = []
     while(index_a &lt; len(A) and index_b &lt; len(B)):
         if(A[index_a] &lt;= B[index_b]):
             result += [A[index_a]]
             index_a += 1
         else:
             result += [B[index_b]]
             index_b += 1
     if(index_a != len(A)):#adds all remaining elements
         result += A[index_a:]
     elif(index_b != len(B)):
         result += B[index_b:]
     return result
  
  def merge_sort(L):
     if(len(L) == 0 or len(L) == 1):
         return L
     else:
         a = merge_sort( L[:len(L)/2] )
         b = merge_sort( L[len(L)/2:] )
         return merge(a , b)
  </code></pre>
  
  <p>So I can understand the complexity of merge_sort function as shown above is log(n) for each recursive call. What I was slightly confused is in the merge function the number of steps taken, first the two assignments but after that I dont know how to get the number of steps taken in the worst case because I cant think of where to stop in the length of A or B and the later addition.</p>
  
  <p>Any help would be really appreciated. Thank You.</p>