title: Implementing merge sort for an array list of objects in java
body: <p>I'm looking to implement a merge sort using an array list of objects. Ideally, I would like to have a static method that takes the array list to be sorted and a boolean as parameters. The boolean, if true, would implement merge sort recursively, and if false would implement the sort using just loops rather than recursion.</p>
  
  <p>Here is the car class used for the object data.</p>
  
  <pre><code>public class Car implements Comparable&lt;Car&gt; {
      private Double milesPerGallon;
      private String make;
      private String model;
      private Integer year;
      private Double milage;
      private Double initialPrice;
  
      public Car(Double milesPerGallon, String make, String model, Integer year, Double milage, Double initialPrice) {
         this.milesPerGallon = milesPerGallon;
         this.make = make;
         this.model = model;
         this.year = year;
         this.milage = milage;
         this.initialPrice = initialPrice;
      }
  
      @Override
      public int compareTo(Car o) {
          int result = this.year.compareTo(o.getYear());
          if (result == 0) {
              result = this.make.compareTo(o.getMake());
              if (result == 0) {
                  return this.model.compareTo(o.getModel());
              } else {
                  return result;
              }
          } else {
              return result;
          }
        }
  }
  </code></pre>
  
  <p>I have gotten to recursive part to work as intended but I am having issues with the iterative sort. Here is my method as it stands. </p>
  
  <pre><code>public static ArrayList&lt;Car&gt; mergeSort(ArrayList&lt;Car&gt; toSort, boolean recursive){
  
      // NON - RECURSIVE METHOD
      if(recursive == false){
          int currentSize;
          int leftStart;
  
          for(currentSize = 1; currentSize &lt;= toSort.size() - 1; currentSize = 2 * currentSize){
              for(leftStart = 0; leftStart &lt; toSort.size() - 1; leftStart += 2 * currentSize){
                  int mid = Math.min(leftStart + currentSize - 1, toSort.size() - 1);
  
                  int rightEnd = Math.min(leftStart + 2 * currentSize - 1, toSort.size() - 1);
  
                  merge(toSort, leftStart, mid, rightEnd);
              }
          }
      }
  
      // RECURSIVE METHOD
      if(recursive == true){
  
          if(toSort == null){
              return toSort;
          }
  
          if(toSort.size() &gt; 1){
              int mid = toSort.size() / 2;
  
              // split left half
              ArrayList&lt;Car&gt; left = new ArrayList&lt;&gt;();
              for(int i = 0; i &lt; mid; i++){
                  left.add(toSort.get(i));
              }
  
              // split right half
              ArrayList&lt;Car&gt; right = new ArrayList&lt;&gt;();
              for(int i = mid; i &lt; toSort.size(); i++){
                  right.add(toSort.get(i));
              }
              mergeSort(left, true);
              mergeSort(right, true);
  
              int i = 0; // index left
              int j = 0; // index right
              int k = 0; // index whole
  
              // merge left and right lists
              while(i &lt; left.size() &amp;&amp; j &lt; right.size()){
                  if(left.get(i).compareTo(right.get(j)) == -1){
                      toSort.set(k, left.get(i));
                      i++;
                  }else{
                      toSort.set(k, right.get(j));
                      j++;
                  }
                  k++;
              }
  
              // remaining list elements
              while(i &lt; left.size()){
                  toSort.set(k, left.get(i));
                  i++;
                  k++;
              }
              while(j &lt; right.size()){
                  toSort.set(k, right.get(j));
                  j++;
                  k++;
              }
          }
      }
  
  
      return toSort;
  }
  </code></pre>
  
  <p>and here is the method used in the iterative part that is currently not working.</p>
  
  <pre><code>public static void merge(ArrayList&lt;Car&gt; toSort, int left, int mid, int right){
      int i, j, k;
      int n1 = mid - left + 1;
      int n2 = right- mid;
  
      // temporary lists
      ArrayList&lt;Car&gt; leftList = new ArrayList&lt;&gt;();
      ArrayList&lt;Car&gt; rightList = new ArrayList&lt;&gt;();
  
      // copy data to temporary lists
      for(i = 0; i &lt; n1; i++){
          leftList.set(i, toSort.get(left + i));
      }
      for(j = 0; j &lt; n2; j++){
          rightList.set(j, toSort.get(mid + left + j));
      }
  
      // merge temporary arrays into toSort
      i = 0;
      j = 0;
      k = mid;
      while(i &lt; n1 &amp;&amp; j &lt; n2){
          if(leftList.get(i).compareTo(rightList.get(j)) == -1 || leftList.get(i).compareTo(rightList.get(j)) == 0){
              toSort.set(k, leftList.get(i));
              i++;
          }else{
              toSort.set(k, rightList.get(j));
              j++;
          }
          k++;
      }
      while(i &lt; n1){
          toSort.set(k, leftList.get(i));
          i++;
          k++;
      }
  </code></pre>