Faster QuickSort

Question

I'm trying to make my QuickSort faster than it is and I have got no more ideas about how to make it more efficient for all types of arrays but mostly very big arrays. It uses random to create the Pivot and it uses InsertionSort when the array is less than 15 elements. What do you think guys? I appreciate for any help here to make the code run faster.

public class QuickSort
 private static Random rand = new Random();
 public void sort(int[] v){
 QuickSort(v, 0, v.length-1);
 }
 private void QuickSort (int[] v, int first, int last) {
 if (first >= last)
 return;
 else {
 if (last - first < 15) {
 InsertionSort(v, first, last);
 return;
 }
 int[] pivotLoc = partitionArray(v, first, last, makePivot(v,first,last));
 QuickSort(v, first, pivotLoc[1]);
 QuickSort(v, pivotLoc[0], last);
 }
 }
 private int[] partitionArray (int[] v, int first, int last, int pivot) {
 while(last => first) {
 while(v[first] < pivot) first++;
 while(v[last] > pivot) last--;
 if (first > last) break;
 swap(v, first, last);
 first++;
 last--;
 }
 return new int[] {first, last};
 }
 private void swap(int[] v, int first, int last) {
 int temp = v[first];
 v[first] = v[last];
 v[last] = temp;
 }
 public void InsertionSort(int[] v, int first, int last) {
 int temp;
 for (int i=first + 1; i <= last; i++) {
 int j = i;
 while (j > 0 && v[j-1] > (v[j]) ) {
 temp = v[j];
 v[j] = v[j-1]; 
 v[j-1] = temp; 
 j--;
 }
 }
 }
 private int makePivot (int[] v, int first, int last){
 return v[rand.nextInt(last-first+1)+first];
 }
}

• coderodde: (1) Your implementation runs into stack overflow. (2) You omitted { after public class QuickSort. (3) There is no => in Java.

Answer 1

As quick sort is a divide and conquer algorithm you can do these steps

QuickSort(v, first, pivotLoc[1]);
QuickSort(v, pivotLoc[0], last);

in parallel. Here is a good start point for this area.

PS also method swap may be reused in your InsertionSort method.

• ratchet freak: But there is a point where the overhead of the thread communication will make it slower than just throwing a single thread at it.
• Andriy Kryvtsun: @ratchetfreak what thread communication and what overhead do you mean?
• ratchet freak: Allocating the Jobs, pushing them to a thread-safe queue, spinning up new threads if needed (which need to pull from that thread-safe queue), waiting on and collecting the "done" signals from the jobs. Only use parallelism when the individual jobs are big enough to warrant all that.
• Dadelante: I have heard about doing it in parallell but where I use this class doesn't allow it.
• Dadelante: Good point about the swap. Got it right! Thanks!