MaheshT.com

ForkJoinPool class which is part of Java 7, allows execution of a task that can be split into multiples tasks and the result of each can be combined into one. The following code demonstrates the use of ForkJoinPool class for sorting using QuickSort algorithm.

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class QuickSortByForkJoinPool extends RecursiveAction {

  private final int SPLIT_THRESHOLD =200000;
  private int sortArray [];
  private int iStart = 0;
  private int iEnd  =0;

 public QuickSortByForkJoinPool(int[] inList,int start, int end){
   this.sortArray = inList;
   this.iStart = start;
   this.iEnd   = end;
 }  

  protected void compute() {
   // System.out.println(iStart + " " + iEnd);
    doQuickSort(sortArray,iStart,iEnd);
  }

  private void doQuickSort(final int inList[], int start, int end){

   // System.out.println("In quick sort");
    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){
        invokeAll(new QuickSortByForkJoinPool(inList, start, leftPointer-1));
      }else {
        doQuickSort(inList, start, leftPointer-1);
      }
    }

    if((end - leftPointer) > 1){
      if ((end - leftPointer) > SPLIT_THRESHOLD ){
        invokeAll(new QuickSortByForkJoinPool(inList, leftPointer+1, end));
      }  else {
        doQuickSort(inList, leftPointer+1, end);
      }
    }

  } 

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

    ForkJoinPool pool = new ForkJoinPool();

    //int [] inArray = {4,2,5,6,9,3,3,3,55657,7878,0,4,4};
    long startTime = System.currentTimeMillis();
    pool.invoke(new QuickSortByForkJoinPool(sortArray , 0, sortArray .length-1));
    System.out.println("Time taken " + (System.currentTimeMillis() - startTime));  

    for (int i=1; i<sortArray.length; i++){
      //System.out.println(" element at " + i + " : " + sortArray[i]  );
   }
  }
}