Why is my quicksort performance worse than my merge?

Question

Am I missing something? The source is short, ready to launch and commented out for a 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 both methods 20 times for comparison. You can copy two sections of 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 the answer: you sort the same list twice, so the second sort always sorts the already sorted list (which is almost always not the same list that was sent to the first sort).

Try this version 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 an ArrayList wrapper class will probably give you a bit of performance. There is overhead for generic List classes that may not be optimized.

• Substituting something like (left + right) / 2 for your random summary code will also remove some overhead that will improve performance.

• The QuickSort specification using InsertionSort for smaller helper arrays is more efficient than splitting.

• Finally, avoiding recursive calls will reduce the use of the stack, which can benefit performance.

Here are some Javascript (sorry, I do not have a Java version, you can translate it if you want). 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; }