MaheshT.com

Running quick sort in parallel is easier in java compare to merge sort because each task in quicksort is independent of each other. (In merge sort, you need to wait for subtasks to be finished before the merge is done)
In the merge task, we keep on dividing the array until it is above the threshold and creating subtask to sort it. All subtasks are submitted to ThreadPool for execution.

Code for classes to execute quick sort in parallel

SortTask interface: This interface has only a method that indicates if the task is ready to execute by a thread in the thread pool. Note that the task for quicksort will be always ready as there is no dependency.

public abstract class SortTask implements Runnable{

  public abstract boolean isReadyToProcess();

}

QuicksortTask class: This is the actual task which a thread in a thread pool executes. The root task of the quick sort divided into many such tasks based on the number of elements in the array that needs to be sorted. If the number of elements under consideration above SPLIT_THRESHOLD then it creates two subtasks otherwise sort those elements in the same task. Here we defined SPLIT_THRESHOLD to 100000 used for sorting a million elements.
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

public class QuickSortTask extends SortTask {
  private final int SPLIT_THRESHOLD = 100000;
  private int sortArray [];
  private int iStart = 0;
  private int iEnd  =0;
  ExecutorService threadPool;
  List futureList;

  public QuickSortTask(ExecutorService threadPool, List futureList, int[] inList,int start, int end){
    this.sortArray = inList;
    this.iStart = start;
    this.iEnd   = end;
    this.threadPool =threadPool;
    this.futureList =futureList;
  }

  @Override
  public boolean isReadyToProcess() {
    return true;
  }

  public void run() {
    sort(sortArray, iStart, iEnd) ;
  }

  private   void sort(final int inList[], int start, int end) {
    int pivot = inList[start]; // consider this as  hole at inList[start],
    int leftPointer = start;
    int rightPointer = end;
    final int LEFT = 1;
    final int RIGHT = -1;
    int pointerSide = RIGHT; //  we start with right as pivot is from left

    while (leftPointer != rightPointer) {
      if (pointerSide == RIGHT) {
        if (inList[rightPointer] < pivot) {           inList[leftPointer] = inList[rightPointer];           leftPointer++;           pointerSide = LEFT;         } else {           rightPointer--;         }       } else if (pointerSide == LEFT) {         if (inList[leftPointer] > pivot) {
          inList[rightPointer] = inList[leftPointer];
          rightPointer--;
          pointerSide = RIGHT;
        } else {
          leftPointer++;
        }
      }
    }

    //put the pivot where leftPointer and rightPointer collide i.e. leftPointer == rightPointer
    inList[leftPointer]=pivot;

    if((leftPointer - start) > 1){
      if ((leftPointer - start) > SPLIT_THRESHOLD){
        futureList.add(threadPool.submit(new QuickSortTask(threadPool,futureList,inList, start, leftPointer-1)));
      }else {
        sort(inList, start, leftPointer-1);
      }
    }

    if((end - leftPointer) > 1){
      if ((end - leftPointer) > SPLIT_THRESHOLD ){
        futureList.add(threadPool.submit(new QuickSortTask(threadPool,futureList,inList, leftPointer+1, end)));
      }  else {
        sort(inList, leftPointer+1, end);
      }
    }

  }

}

QuickSortInParallel class: Main class to put everything together. Here we create an instance of ThreadPoolExecutor with 10 threads and create a root task to sort a million random elements. Also, a list to hold Futures returned by submit method of ExecutorService. The get method of Future wait until the task is completed. We remove the Feature from the list when the corresponding task is done.

Empty Features List means all tasks are done and the list is sorted.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Vector;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class QuickSortInParallel {

  public static void main(String [] args){
    final int  NO_OF_ELEMENT = 10000000;
    Random random = new Random();

    int [] sortArray = new int [NO_OF_ELEMENT ];
    for (int i=0; i< NO_OF_ELEMENT ;i++){
      sortArray[i] = random.nextInt(NO_OF_ELEMENT );
    }

    final ExecutorService executor = Executors.newFixedThreadPool(10);
    List futures = new Vector();
    QuickSortTask rootTask = new QuickSortTask (executor,futures,sortArray,0,sortArray.length-1)  ;
    long startTime = System.currentTimeMillis();
    futures.add(executor.submit(rootTask));
    while(!futures.isEmpty()){
 //     System.out.println("Future size " +futures.size());
      Future topFeature = futures.remove(0);
      try{
        if(topFeature!=null)topFeature.get();
      }catch(InterruptedException ie){
        ie.printStackTrace();
      }catch(ExecutionException ie){
        ie.printStackTrace();
      }
    }
    System.out.println("Time taken " + (System.currentTimeMillis() - startTime));
     for (int i=sortArray.length-1000; i<sortArray.length; i++){
       System.out.println(" element at " + i + " : " + sortArray[i]  );
    }
    executor.shutdown();
  }

}