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).

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.