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).
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]; } } } }
In the above declared task, we override the compute method to partition the array given to be sorted:
int[] arrayPart1 = null; int[] arrayPart2 = null; partitionArray(arrayToDivide, arrayPart1, arrayPart2);
if the array given to the task cannot be divided further i.e has only one element, then return that array
return arrayToDivide;
If the partitions were created, then assign each partition to a new task and invoke the tasks created:
DivideTask task1 = new DivideTask(arrayPart1); DivideTask task2 = new DivideTask(arrayPart2); invokeAll(task1, task2);
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:
//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;
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:
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())); } }
Output:
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)
Another useful variant of Merge sort algorithm can be found here.