• Menu
  • Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

JavaBeat

Java Tutorial Blog

  • Java
    • Java 7
    • Java 8
    • Java EE
    • Servlets
  • Spring Framework
    • Spring Tutorials
    • Spring 4 Tutorials
    • Spring Boot
  • JSF Tutorials
  • Most Popular
    • Binary Search Tree Traversal
    • Spring Batch Tutorial
    • AngularJS + Spring MVC
    • Spring Data JPA Tutorial
    • Packaging and Deploying Node.js
  • About Us
    • Join Us (JBC)
  • Java
    • Java 7
    • Java 8
    • Java EE
    • Servlets
  • Spring Framework
    • Spring Tutorials
    • Spring 4 Tutorials
    • Spring Boot
  • JSF Tutorials
  • Most Popular
    • Binary Search Tree Traversal
    • Spring Batch Tutorial
    • AngularJS + Spring MVC
    • Spring Data JPA Tutorial
    • Packaging and Deploying Node.js
  • About Us
    • Join Us (JBC)

Merge Sort implementation using Fork-Join Framework in Java 7

June 13, 2012 //  by Mohamed Sanaulla//  Leave a Comment

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.

Category: JavaTag: Fork Join, java 7, Merge Sort

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.

Previous Post: « A simple Location and Weather mashup using Gaelyk Framework
Next Post: Implementing WatchService API in Java 7 to monitor the directory changes »

Reader Interactions

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

Follow Us

  • Facebook
  • Pinterest

FEATURED TUTORIALS

New Features in Spring Boot 1.4

Difference Between @RequestParam and @PathVariable in Spring MVC

What is new in Java 6.0 Collections API?

The Java 6.0 Compiler API

Introductiion to Jakarta Struts

What’s new in Struts 2.0? – Struts 2.0 Framework

JavaBeat

Copyright © by JavaBeat · All rights reserved
Privacy Policy | Contact