title: How to merge two big Lists in one sorted List in Java?
body: <p>I had an interview today, and they gave me: </p>
  
  <p>List A has:</p>
  
  <pre><code>f  
  google   
  gfk  
  fat  
  ...
  </code></pre>
  
  <p>List B has:   </p>
  
  <pre><code>hgt    
  google  
  koko  
  fat  
  ffta  
  ...
  </code></pre>
  
  <p>They asked me to merge these two list in one sorted List C.</p>
  
  <p>What I said:</p>
  
  <p>I added List B to List A, then I created a Set from List A, then create a List from the Set. The interviewer told me the lists are big, and this method will not be good for performance, he said it will be a nlog(n).</p>
  
  <p>What would be a better approach to this problem?</p>