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:
In summary the Merge sort algorithm:
- Divides the array into 1 parts
- Sort each part individually and merge them to form a smaller sorted array.
- 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.