title: Why is my quicksort performance worse than my mergesort?
body: <p>Am I missing something? The source is short, ready to run and commented for better understanding. I need to know what I'm doing wrong.</p>
  
  <pre><code>package com.company;
  
  import java.io.BufferedReader;
  import java.io.FileReader;
  import java.io.IOException;
  import java.util.*;
  
  public class Main {
  
      public static ArrayList&lt;Integer&gt; randomArrayList(int n)
      {
          ArrayList&lt;Integer&gt; list = new ArrayList&lt;&gt;();
          Random random = new Random();
  
          for (int i = 0; i &lt; n; i++)
          {
              list.add(random.nextInt(n));
          }
          return list;
      }
  
      public static List&lt;Integer&gt; MergeSort(List&lt;Integer&gt; A) throws  Exception{
  
          if (A.size()==1)
              return A;
  
          int mid = A.size()/2;
  
          List&lt;Integer&gt; left = A.subList(0,mid);
          List&lt;Integer&gt; right = A.subList(mid,A.size());
  
          left = MergeSort(left);
          right = MergeSort(right);
          A = Merge(left,right);
  
          return A;
      }
  
      public static List&lt;Integer&gt; Merge(List&lt;Integer&gt; L,List&lt;Integer&gt; R) throws  Exception{
  
          List&lt;Integer&gt; output = new ArrayList&lt;Integer&gt;(Collections.nCopies(L.size() + R.size(), 0));
  
          int i = 0; int j = 0; int k = 0;
          while (i &lt; L.size() &amp;&amp; j &lt; R.size()) {
              if (L.get(i) &lt; R.get(j)) {
                  output.set(k, L.get(i));
                  i=i+1;
              }
              else {
                  output.set(k, R.get(j));
                  j=j+1;
              }
              k++;
          }
          while (i &lt; L.size()) {
              output.set(k, L.get(i));
              i=i+1;
              k++;
          }
          while (j &lt; R.size()) {
              output.set(k, R.get(j));
              j=j+1;
              k++;
          }
  
          return output;
      }
  
      public static List&lt;Integer&gt; QuickSort(List&lt;Integer&gt; A) throws  Exception{
  
          if (A.size()==1 || A.size()==0)
              return A;
  
          //The pivot is a random element of the array A
          int randomIndex = new Random().nextInt(A.size());
          Integer P = A.get(randomIndex);
  
          //Swap first element of A with selected pivot
          Integer tmp;
          A.set(randomIndex,A.get(0));
          A.set(0, P);
  
          //Initiate i and l (partition analysis progress counters)
          int l = 0, i = l + 1, r = A.size();
  
  
          for (int j = l + 1; j &lt; r; j++ ){
              if (A.get(j)&lt; P ){
                  //Swap A[j] and A[i]
                  tmp = A.get(j);
                  A.set(j,A.get(i));
                  A.set(i,tmp);
                  //Increase i by 1 (counting the pos of already partitioned)
                  i = i + 1;
              }
          }
  
          //Swap A[l] (Pivot) and A[i-1] most left element bigger than pivot
          tmp = A.get(l);
          A.set(l,A.get(i-1));
          A.set(i - 1, tmp);
  
          QuickSort(A.subList(0,i-1));
          QuickSort(A.subList(i,A.size()));
  
          return A;
      }
  </code></pre>
  
  <p>In the main function I run 20 times both methods to compare. You can copy the two sections of the code and run it</p>
  
  <pre><code>    public static void main(String[] args) throws Exception{
  
          long startTime, endTime, duration;
  
          //Compare 20 times QuickSort vs MergeSort
          for (int i=0;i&lt;20;i++){
  
              List&lt;Integer&gt; arreglo = randomArrayList(100000);
  
              startTime = System.nanoTime();
              QuickSort(arreglo);
              endTime = System.nanoTime();
  
              duration = (endTime - startTime)/1000000;
              System.out.println("Quicksort: " + Long.toString(duration));
  
              startTime = System.nanoTime();
              MergeSort(arreglo);
              endTime = System.nanoTime();
  
              duration = (endTime - startTime)/1000000;
              System.out.println("MergeSort: "+Long.toString(duration));
  
              //System.out.println(Arrays.toString(QuickSort(arreglo).toArray()));
              //System.out.println(Arrays.toString(MergeSort(arreglo).toArray()));
          }
      }
  }
  </code></pre>