title: QuickSort vs MergeSort, what am I doing wrong?
body: <p>I am trying to implement several sorting algorithms in Java, to compare the performances. From what I've read, I was expecting quickSort to be faster than mergeSort, but on my code it is not, so I assume there must be a problem with my quickSort algorithm:</p>
  
  <pre><code>public class quickSortExample{
  public static void main(String[] args){
      Random gen = new Random();
      int n = 1000000;
      int max = 1500000;
      ArrayList&lt;Integer&gt; d = new ArrayList&lt;Integer&gt;();
      for(int i = 0; i &lt; n; i++){
          d.add(gen.nextInt(max));
      }
      ArrayList&lt;Integer&gt; r;
      long start, end;
  
      start = System.currentTimeMillis();
      r = quickSort(d);
      end = System.currentTimeMillis();
      System.out.println("QuickSort:");
      System.out.println("Time: " + (end-start));
      //System.out.println(display(d));
      //System.out.println(display(r));
  }
  
  public static ArrayList&lt;Integer&gt; quickSort(ArrayList&lt;Integer&gt; data){
      if(data.size() &gt; 1){
          int pivotIndex = getPivotIndex(data);
          int pivot = data.get(pivotIndex);
          data.remove(pivotIndex);
          ArrayList&lt;Integer&gt; smallers = new ArrayList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; largers = new ArrayList&lt;Integer&gt;();
          for(int i = 0; i &lt; data.size(); i++){
              if(data.get(i) &lt;= pivot){
                  smallers.add(data.get(i));
              }else{
                  largers.add(data.get(i));
              }
          }
          smallers = quickSort(smallers);
          largers = quickSort(largers);
          return concat(smallers, pivot, largers);
      }else{
          return data;
      }
  }
  
  public static int getPivotIndex(ArrayList&lt;Integer&gt; d){
      return (int)Math.floor(d.size()/2.0);
  }
  
  public static ArrayList&lt;Integer&gt; concat(ArrayList&lt;Integer&gt; s, int p, ArrayList&lt;Integer&gt; l){
      ArrayList&lt;Integer&gt; arr = new ArrayList&lt;Integer&gt;(s);
      arr.add(p);
      arr.addAll(l);
  
      return arr;
  }
  
  public static String display(ArrayList&lt;Integer&gt; data){
      String s = "[";
      for(int i=0; i &lt; data.size(); i++){
          s += data.get(i) + ", ";
      }
      return (s+"]");
  }
  
  }
  </code></pre>
  
  <p>Results (on 1 million integer between 0 and 1500000):</p>
  
  <p>mergeSort (implemented with arrayList too): 1.3sec (average) (0.7sec with int[] instead)</p>
  
  <p>quickSort: 3sec (average)</p>
  
  <p>Is it just the choice of my pivot which is bad, or are there some flaws in the algo too.</p>
  
  <p>Also, is there a faster way to code it with int[] instead of ArrayList()? (How do you declare the size of the array for largers/smallers arrays?)</p>
  
  <p>PS: I now it is possible to implement it in an inplace manner so it uses less memory, but this is not the point of this.</p>
  
  <p>EDIT 1: I earned 1 sec by changing the concat method.
  Thanks!</p>