title: Merge sort in ArrayList in Java
body: <p>I am learning how to implement basic algorithms in Java, so i am a newbie in this environment. I am trying to implement Merge Sort algorithm using ArrayList where program will read data (Integer in each line) from file and produce sorting result using Merge Sort. However, my code is showing same result as it has not sorted anything out! I would be very glad if someone can identify where did I do my mistake. As i am a beginner, the code is very simple, not optimized and not very fast in performance probably.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>public class MergeSortExp1 {
  
      public static void main(String[] args) {
  
          ArrayList&lt;Integer&gt;number = new ArrayList&lt;Integer&gt;();
  
          Scanner myScanner = null;
          try {
          myScanner = new Scanner(new File("/Users/Sabbir/Desktop/workload.txt"));
          } catch (FileNotFoundException e) {
  
          e.printStackTrace();
          }
  
          while(myScanner.hasNextInt()){
              number.add(myScanner.nextInt());
          }
  
          System.out.println("Before sorting" +number);
          number=mergeSort(number);
          System.out.println("Sorted Array =" +number);
      }
  
          public static ArrayList&lt;Integer&gt; mergeSort( ArrayList&lt;Integer&gt; Input)
          {
              if (Input.size() ==1){
                  return Input;
              }
              else {
                  int mid= Input.size()/2;
                  ArrayList&lt;Integer&gt; left= new ArrayList&lt;Integer&gt;(mid);
                  ArrayList&lt;Integer&gt; right=new ArrayList&lt;Integer&gt;(Input.size()-mid);
  
                 for (int i = 0; i &lt; mid; i++) {
                     left.add(Input.get(i));
                     } 
  
                 for (int i = 0; i &lt; Input.size()-mid; i++) {
                     right.add(Input.get(i));
                 } 
  
                 left=mergeSort(left); 
                 right=mergeSort(right);
                 merge(left,right,Input);
              }
                 return Input;
          }
  
  
          public static void merge (ArrayList&lt;Integer&gt;left,ArrayList&lt;Integer&gt;right,ArrayList&lt;Integer&gt;Input)
          {
              int i1=0;// left Index
              int i2=0;// right Index
              int InputIndex=0;
  
              for (int i = 0; i &lt; Input.size(); i++) {
                  if (i2&gt;=right.size() || (i1&lt;left.size() &amp;&amp; left.get(i)&lt;=right.get(i))) 
                  {
                      Input.set(InputIndex,left.get(i1));
                      InputIndex++;
                  }
                  else {
                      Input.set(InputIndex, right.get(i2));
                      InputIndex++;
                  }
              }
  
          }
  }
  </code></pre>