title: Merging and sorting lists: Complexity
body: <p>I am writing a code in order to return a list that is the sorted merge of other two sorted lists. The exercise requires that the complexity has O(n+m) where n and m are the elements in the two lists to merge. I solved the exercise and think the complexity is the correct one, but I'm not definitely sure, may I kindly as you to give it a look?</p>
  
  <pre><code>def merge1(a,b):
      last=-1
      saved=[]
      while a!=[] and b!=[]:
          current_max=max(a[last], b[last])
          saved.append(current_max)
          if current_max==a[-1]:
              a.pop()
          else:
              b.pop()
  </code></pre>
  
  <p>Until here the complexity is for sure the correct one, I am unsure about the following</p>
  
  <pre><code>    if a==[]:
          for el in range(len(b)):
              saved.append(max(b))
              b.pop()
      else:
          for el in range(len(a)):
              saved.append(max(a))
              a.pop()
      saved.reverse()
      return saved
  </code></pre>
  
  <p>I imagine that the complexity could be reduced using only various <code>if</code> and avoiding the last <code>for</code> cycle, but could you please give me your opinion about my code anyway? Thx guys.</p>