title: Merging two sorted ArrayLists
body: <p>I am supposed to create a method that will merge two given pre-sorted ArrayLists of Strings into one. All of it has to be done in one loop. The way I have gone about it is comparing the two ArrayLists at each index and adding them in alphabetical order based on those comparisons. The problem with this is that if you are given two ArrayLists ["Bob", "Jill"] and ["Watson", "Zane"], the output would be ["Bob", "Watson", "Jill", "Zane"]. This is clearly not sorted.</p>
  
  <p>That being said, I know what the problem is, I just don't know how to implement a fix for it.</p>
  
  <p>Code:</p>
  
  <pre><code>public static ArrayList&lt;String&gt; merge(ArrayList&lt;String&gt; al1, ArrayList&lt;String&gt; al2){
    ArrayList&lt;String&gt; al = new ArrayList&lt;String&gt; (al1.size() + al2.size());
    for (int i = 0; i &lt; Math.max(al1.size(), al2.size()); i++) { // Loops until max size of the two arraylists is reached
        if (i &lt; al1.size() &amp;&amp; i &lt; al2.size()) { // Checks if the index is still in range of both arraylists
            if (al1.get(i).compareTo(al2.get(i)) &lt; 0) { // Compares the two arraylists at the same index
                al.add(al1.get(i));
                al.add(al2.get(i));
            } else {
                al.add(al2.get(i));
                al.add(al1.get(i));
            }
        } else if (i &lt; al1.size() &amp;&amp; i &gt; al2.size()) { // Checks if the index is greater than the size of al2
            al.add(al1.get(i));
        } else { // Anything else, just add al2
            al.add(al2.get(i));
        }
    }
    return al;
  </code></pre>