Java – why is my quicksort performance worse than my mergeport?

Did I miss anything? The source is short and can be run and commented at any time for better understanding I need to know what I did wrong

package com.company;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static ArrayList<Integer> randomArrayList(int n)
    {
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();

        for (int i = 0; i < n; i++)
        {
            list.add(random.nextInt(n));
        }
        return list;
    }

    public static List<Integer> MergeSort(List<Integer> A) throws  Exception{

        if (A.size()==1)
            return A;

        int mid = A.size()/2;

        List<Integer> left = A.subList(0,mid);
        List<Integer> right = A.subList(mid,A.size());

        left = MergeSort(left);
        right = MergeSort(right);
        A = Merge(left,right);

        return A;
    }

    public static List<Integer> Merge(List<Integer> L,List<Integer> R) throws  Exception{

        List<Integer> output = new ArrayList<Integer>(Collections.nCopies(L.size() + R.size(),0));

        int i = 0; int j = 0; int k = 0;
        while (i < L.size() && j < R.size()) {
            if (L.get(i) < 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 < L.size()) {
            output.set(k,L.get(i));
            i=i+1;
            k++;
        }
        while (j < R.size()) {
            output.set(k,R.get(j));
            j=j+1;
            k++;
        }

        return output;
    }

    public static List<Integer> QuickSort(List<Integer> 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 < r; j++ ){
            if (A.get(j)< 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;
    }

In the main function, I run 20 times to compare the two methods You can copy two parts of the code and run it

public static void main(String[] args) throws Exception{

        long startTime,endTime,duration;

        //Compare 20 times QuickSort vs MergeSort
        for (int i=0;i<20;i++){

            List<Integer> 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()));
        }
    }
}

Solution

This is my comment as the answer: you are sorting the same list twice, so the second sort always sorts the list that has been sorted (this is almost always different from the list sorted the first time)

Try this variant of your main code:

public static void main(String[] args) throws Exception{

    long startTime,duration;

    //Compare 20 times QuickSort vs MergeSort
    for (int i=0;i<20;i++){

        List<Integer> arreglo = randomArrayList(100000);
        List<Integer> arreglo2 = new ArrayList<>(arreglo); // Make a copy

        startTime = System.nanoTime();
        QuickSort(arreglo);                                // Sort the original
        endTime = System.nanoTime();

        duration = (endTime - startTime)/1000000;
        System.out.println("Quicksort: " + Long.toString(duration));

        startTime = System.nanoTime();
        MergeSort(arreglo2);                               // Sort the copy
        endTime = System.nanoTime();

        duration = (endTime - startTime)/1000000;
        System.out.println("MergeSort: "+Long.toString(duration));
    }
}