title: Java ArrayList merge sort algorithm
body: <p>I'm having some issues with my merge sort algorithm in Java. It seems to be doing a lot of weird things now and I'm having trouble getting it to work. I believe the issue might lie somewhere in the <code>mergeArrayLists</code> function, but I'm not sure. Any help would be appreciated!</p>
  
  <pre><code>public class MergeSort extends Sort {
  
     public MergeSort() {
     }
  
     // Inherited from Sort
     public &lt;T extends Comparable&lt;T&gt;&gt; void sortArrayList(ArrayList&lt;T&gt; arrayList) {
        arrayList = mergeSort(arrayList);
     }
  
     // Returns the sorted form of the given array list (sorted via the merge sort algorithm)
     public &lt;T extends Comparable&lt;T&gt;&gt; ArrayList&lt;T&gt; mergeSort(
           ArrayList&lt;T&gt; arrayList) {
        if (arrayList.size() &lt;= 1) {
           return arrayList;
        } else {
           ArrayList&lt;T&gt; firstList = new ArrayList&lt;T&gt;();
           ArrayList&lt;T&gt; secondList = new ArrayList&lt;T&gt;();
  
           for (int i = 0; i &lt; arrayList.size(); i++) {
              T thisValue = arrayList.get(i);
              if (i &lt; arrayList.size() / 2) {
                 firstList.add(thisValue);
              } else {
                 secondList.add(thisValue);
              }
           }
           //System.out.println(firstList+" "+mergeSort(firstList));
           ArrayList&lt;T&gt; firstSort = mergeSort(firstList);
           ArrayList&lt;T&gt; secondSort = mergeSort(secondList);
           return mergeArrayLists(firstSort, secondSort);
        }
     }
  
     // Merges two array lists together, in order
     public &lt;T extends Comparable&lt;T&gt;&gt; ArrayList&lt;T&gt; mergeArrayLists(
           ArrayList&lt;T&gt; firstList, ArrayList&lt;T&gt; secondList) {
        ArrayList&lt;T&gt; resultList = new ArrayList&lt;T&gt;();
  
        int firstIndex, secondIndex = 0;
        for (firstIndex = 0; firstIndex &lt; firstList.size() - 1; firstIndex++) {
           while (secondIndex &lt; secondList.size() - 1) {
              if (firstList.get(firstIndex)
                    .compareTo(secondList.get(secondIndex)) &lt; 0) {
                 break;
              } else {
                 resultList.set(firstIndex + secondIndex,
                       secondList.get(secondIndex));
                 secondIndex++;
              }
           }
           resultList.set(firstIndex + secondIndex, firstList.get(firstIndex));
        }
        System.out.println(firstList + " + " + secondList + " = " + resultList);
  
        return resultList;
     }
  }
  </code></pre>