Why is my quicksort performance worse than my mergesort?

Question

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.

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 both methods to compare. You can copy the two sections 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()));
        }
    }
}

Answer 1

Here's my comment as an answer: You are sorting the same list twice, so the second sort is always sorting an already-sorted list (which is almost always not the same list as was fed to the first sort).

Try this variant of your main code:

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);
        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));
    }
}

Answer 2

• Using an int[] array instead of the ArrayList wrapper class will probably gain you a bit of performance. There is overhead with the generic List classes that may not get optimized away.

• Substituting something like (left + right) / 2 for your Random pivot code will also remove some overhead which will improve performance.

• QuickSort specific, using InsertionSort on smaller sub arrays is more efficient than the partitioning.

• Finally, avoiding recursive calls will lower stack usage which can benefit performance.

Here's some Javascript (sorry I don't have a Java version, you can translate it if you'd like). The implementation should be very fast.

/*
QUICK SORT IN PLACE
Use iterative approach with stack
Use insertion sort for small subsets
*/
function quickSortIP(arr) {
    var stack = [];
    var left = 0;
    var right = arr.length - 1;
    var i, j, swap, temp;
    while(true) {
        if(right - left <= 25){
            for(j=left+1; j<=right; j++) {
                swap = arr[j];
                i = j-1;
                while(i >= left && arr[i] > swap) {
                    arr[i+1] = arr[i--];
                }
                arr[i+1] = swap;
            }
            if(stack.length === 0)    break;
            right = stack.pop();
            left = stack.pop();
        } else {
            var median = (left + right) >> 1;
            i = left + 1;
            j = right;
            swap = arr[median]; arr[median] = arr[i]; arr[i] = swap;
            if(arr[left] > arr[right]) {
                swap = arr[left]; arr[left] = arr[right]; arr[right] = swap;
            } if(arr[i] > arr[right]) {
                swap = arr[i]; arr[i] = arr[right]; arr[right] = swap;
            } if(arr[left] > arr[i]) {
                swap = arr[left]; arr[left] = arr[i]; arr[i] = swap;
            }
            temp = arr[i];
            while(true){
                do i++; while(arr[i] < temp);
                do j--; while(arr[j] > temp);
                if(j < i)    break;
                swap = arr[i]; arr[i] = arr[j]; arr[j] = swap;
            }
            arr[left + 1] = arr[j];
            arr[j] = temp;
            if(right - i + 1 >= j - left){
                stack.push(i);
                stack.push(right);
                right = j - 1;
            }else{
                stack.push(left);
                stack.push(j - 1);
                left = i;
            }
        }
    }
    return arr;
}