title: Java Recursive MergeSort for ArrayLists
body: <p>I have been having a problem with my mergesort function, as I am not able to sort a series of integers or strings whenever inputting it into the program. I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is. Numbers are randomly inputted.</p>
  
  <p>CODE: </p>
  
  <pre><code>/**
       * Takes in entire vector, but will merge the following sections together:
       * Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
       * Precondition: each sublist is already in ascending order
       *
       * @param a
       *            reference to an array of integers to be sorted
       * @param first
       *            starting index of range of values to be sorted
       * @param mid
       *            midpoint index of range of values to be sorted
       * @param last
       *            last index of range of values to be sorted
       */
      private void merge(ArrayList&lt;Comparable&gt; a, int first, int mid, int last) {
          int x;
          int i;
          ArrayList&lt;Comparable&gt; left = new ArrayList&lt;Comparable&gt;();
          ArrayList&lt;Comparable&gt; right = new ArrayList&lt;Comparable&gt;();
          mergeSort(a,first,mid);
          for(i = 0; i &lt; a.size() - mid; i++){
              left.add(i,a.get(i));
              a.remove(i);
          }
          mergeSort(a,mid,last);
          for (x = mid; x &lt; a.size(); x++) {
              right.add(x,a.get(x));
              a.remove(x);
          }
          if ((left.get(i).compareTo(right.get(x))) &gt; 0) {
              i++;
              a.add(i);
          } else if (i &lt; x) {
              x++;
              a.add(x);
          }
  
  
          System.out.println();
          System.out.println("Merge");
          System.out.println();
  
      }
  
      /**
       * Recursive mergesort of an array of integers
       *
       * @param a
       *            reference to an array of integers to be sorted
       * @param first
       *            starting index of range of values to be sorted
       * @param last
       *            ending index of range of values to be sorted
       */
      public void mergeSort(ArrayList&lt;Comparable&gt; a, int first, int last) {
  
          int mid = (first + last)/2;
          if(first == last){
  
          }else if(last - first == 1){
              merge(a,first, mid ,last);              
          }else{
              last = mid;
          }
  
  
                  }
  </code></pre>