Merge Sort implementation using Fork-Join Framework in Java 7

In our previous post we went through the basics of Fork-Join Framework introduced as part of Java 7. In this post lets apply the same Fork-Join to implement Merge sort algorithm. The pseudo code for Merge sort can be found here.

also read:

• Java 7.0 Tutorials
• New Features in Java 7.0
• G1 Garbage Collector in Java 7.0

In summary the Merge sort algorithm:

1. Divides the array into 1 parts
2. Sort each part individually and merge them to form a smaller sorted array.
3. Merge individual sorted arrays to get the complete sorted array.

We create a task for dividing the array into 2 parts and then merge the arrays in the same task (i.e we dont spawn a new task for merging the arrays).
[code lang=”java”]
class DivideTask extends RecursiveTask<int[]> {

int[] arrayToDivide;

public DivideTask(int[] arrayToDivide) {
this.arrayToDivide = arrayToDivide;
}

@Override
protected int[] compute() {
List<RecursiveTask> forkedTasks = new ArrayList<>();

/*
* We divide the array till it has only 1 element.
* We can also custom define this value to say some
* 5 elements. In which case the return would be
* Arrays.sort(arrayToDivide) instead.
*/
if (arrayToDivide.length > 1) {

List<int[]> partitionedArray = partitionArray();

DivideTask task1 = new DivideTask(partitionedArray.get(0));
DivideTask task2 = new DivideTask(partitionedArray.get(1));
invokeAll(task1, task2);

//Wait for results from both the tasks
int[] array1 = task1.join();
int[] array2 = task2.join();

//Initialize a merged array
int[] mergedArray =
new int[array1.length + array2.length];

mergeArrays(task1.join(), task2.join(), mergedArray);

return mergedArray;
}
return arrayToDivide;
}

private List<int[]> partitionArray(){

int [] partition1 = Arrays.copyOfRange(arrayToDivide, 0,
arrayToDivide.length / 2);

int [] partition2 = Arrays.copyOfRange(arrayToDivide,
arrayToDivide.length / 2,
arrayToDivide.length);
return Arrays.asList(partition1,partition2);

}

private void mergeArrays(
int[] array1,
int[] array2,
int[] mergedArray) {

int i = 0, j = 0, k = 0;

while ((i < array1.length) && (j < array2.length)) {

if (array1[i] < array2[j]) {
mergedArray[k] = array1[i++];
} else {
mergedArray[k] = array2[j++];
}

k++;
}

if (i == array1.length) {

for (int a = j; a < array2.length; a++) {
mergedArray[k++] = array2[a];
}

} else {

for (int a = i; a < array1.length; a++) {
mergedArray[k++] = array1[a];
}

}
}
}
[/code]

In the above declared task, we override the compute method to partition the array given to be sorted:
[code lang=”java”]
int[] arrayPart1 = null;
int[] arrayPart2 = null;
partitionArray(arrayToDivide, arrayPart1, arrayPart2);
[/code]

if the array given to the task cannot be divided further i.e has only one element, then return that array
[code lang=”java”]
return arrayToDivide;
[/code]

If the partitions were created, then assign each partition to a new task and invoke the tasks created:
[code lang=”java”]
DivideTask task1 = new DivideTask(arrayPart1);
DivideTask task2 = new DivideTask(arrayPart2);
invokeAll(task1, task2);
[/code]

We would then have to wait for the results from both the tasks spawned and then merge their results to create a smaller sorted array:
[code lang=”java”]
//Wait for results from both the tasks
int[] array1 = task1.join();
int[] array2 = task2.join();

//Initialize a merged array
int[] mergedArray =
new int[array1.length + array2.length];

mergeArrays(task1.join(), task2.join(), mergedArray);

return mergedArray;
[/code]

This way each of the task which spawns more sub tasks would wait for their sub tasks to return a sorted array and then return back the sorted array to the parent task. This operation can be invoked as:
[code lang=”java”]
public class ForkJoinTest {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int totalNumbers = scanner.nextInt();

int[] numbers = new int[totalNumbers];

for (int i = 0; i < totalNumbers; i++) {
numbers[i] = scanner.nextInt();
}

System.out.println("Unsorted array: "
+ Arrays.toString(numbers));

DivideTask task = new DivideTask(numbers);
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(task);

System.out.println("Sorted array: "
+ Arrays.toString(task.join()));

}
}
[/code]

Output:
[code]
run:
8
8 3 2 9 7 1 5 4
Unsorted array: [8, 3, 2, 9, 7, 1, 5, 4]
Sorted array: [1, 2, 3, 4, 5, 7, 8, 9]
BUILD SUCCESSFUL (total time: 2 seconds)
[/code]

Another useful variant of Merge sort algorithm can be found here.