title: Best Method for Adding a Sorted Array to a Reallocated Sorted Array While Sorting the Combined Array
body: <p>I'm trying to figure out the best solution for this particular problem.</p>
  
  <p>Here is the rundown of what I am trying to do:</p>
  
  <ul>
  <li>I have two arrays, A and B.</li>
  <li>B was previously reallocated to make room for the elements in A.</li>
  <li>A is always a fully populated array.</li>
  <li>B always has at least one element.</li>
  <li>Both A and B are already sorted.</li>
  </ul>
  
  <p>I want to add the elements of A to B while keeping the array sorted.</p>
  
  <p>Ex:</p>
  
  <pre><code>//Given:
  A = [1,3,5]
  B = [2,4,6, , , ]
  
  //Desired Result:
  B = [1,2,3,4,5,6]
  </code></pre>
  
  <p>The fastest way of doing this that I have thought of so far would be:</p>
  
  <ul>
  <li>Add all of the elements of A to B, would take O(n).</li>
  <li>Sort the combined array, using something like merge sort for O(nlogn).</li>
  </ul>
  
  <p>I'm trying to figure out of there is a way doing this faster than O(nlogn).</p>
  
  <p>Space complexity is not an issue in this case.</p>