title: Merging two sorted arrays into a third one can be done in O(n)?
body: <p>I'm trying to merge to sorted arrays into a third sorted array , but I can't see
  any way to do that in <code>O(n)</code> , only in <code>O(n*n)</code> .Am I wrong ? is there a way to do that in <code>O(n)</code> ? </p>
  
  <p><strong>Edit :</strong> </p>
  
  <p>Actually the question is a little different : </p>
  
  <p>I have 2 sorted skip lists and I want to merge them into a new sorted skip list ,without changing 
  the input (i.e. the two skip lists) . </p>
  
  <p>I was thinking about :</p>
  
  <ul>
  <li><p>put the lists in two arrays </p></li>
  <li><p>merge the two arrays using MergeSort (this takes <code>O(n)</code> runtime)</p></li>
  <li><p>build a new skip list from the sorted array .... // I'm not sure about its runtime </p></li>
  </ul>
  
  <p>any ideas ? </p>
  
  <p>Regards</p>