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