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:

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.

Comments

comments

About Mohamed Sanaulla

In his day job he works on developing enterprise applications using ADF. He is also the moderator of JavaRanch forums and an avid blogger.

Trackbacks

  1. JavaPins says:

    Merge Sort implementation using Fork-Join Framework in Java 7…

    Thank you for submitting this cool story – Trackback from JavaPins…

Speak Your Mind

*