title: Recursively Merging 2 "Virtual Lists" together into one
body: <p>Before you read the problem: No, I'm not trying to get you to write code for me, I just want a few pointers</p>
  
  <p>I have a problem with a MergeSort algorithm I'm writing up. The specifications of the code state that I can only use ONE ArrayList for the act of merging. For example:</p>
  
  <p>With an ArrayList of [5, 1, 3, 9, 2], I would recursively split the list up into</p>
  
  <ul>
  <li>[5, 1, 3] and [9, 2]</li>
  <li>I would split each of these sub lists AGAIN into:</li>
  <li>[5, 1] and [3] ---------- and [9] and [2];</li>
  </ul>
  
  <p>Now, I would sort the arrayList [5, 1] into [1, 5] and then I would have one whole array containing the numbers:</p>
  
  <ul>
  <li>[1, 5, 3, 9, 2]</li>
  </ul>
  
  <p>Remember, at this point, I have not created ANY new ArrayLists, I have just sorted within the small sublists that I have. So, going back to recursion, I would then merge the list with [1, 5] with the list [3]. Now, how would I go about doing something like that without having to create a brand new ArrayList to store temporary information? </p>
  
  <p>Anyways, once I have [1, 3, 5, 9, 2], I would then sort out the second sublist, [9, 2], and get [1, 3, 5, 2, 9]. Then I would need to "virtually" merge [1, 3, 5] and [2, 9] to get [1, 2, 3, 5, 9]. How would I go about "virtually" merging these lists (in essence, shifting indices over without having to create a new ArrayList).</p>
  
  <p>This is the code I have so far:</p>
  
  <pre><code>    int counterFromStart = first;
      int counterFromMid = mid + 1;
  
      while (counterFromStart &lt; counterFromMid &amp;&amp; (counterFromMid &lt;= last)){
          if (a.get(counterFromStart).compareTo(a.get(counterFromMid)) &gt; 0){
              Comparable temp = a.get(counterFromStart);
              a.set(counterFromStart, a.get(counterFromMid));
              a.set(counterFromMid, temp);
              counterFromMid++;
          }     else {
              counterFromStart++;
          }
      }
  </code></pre>
  
  <p>Also, I have solved this lab in a different way, but not with the method of merging:</p>
  
  <p>With each sublist, I ran through it with insertionSort to sort the two sublists, but again, this is not what "merging" really is: My code, for that method however, is below:</p>
  
  <pre><code>    for (int outer = first + 1; outer &lt;= last; outer++){
          int positionInSubList = outer;
          Comparable insertObject = a.get(positionInSubList);
  
      while (positionInSubList &gt; 0 &amp;&amp; a.get(positionInSubList - 1).compareTo(insertObject) &gt; 0){
              a.set(positionInSubList, a.get(positionInSubList - 1));
              positionInSubList--;
          }
          a.set(positionInSubList, insertObject);
      }
  </code></pre>