1  import java.util.concurrent.RecursiveAction;
  2  import java.util.concurrent.ForkJoinPool;
  3  
  4  public class ParallelMergeSort {
  5    public static void main(String[] args) {
  6      final int SIZE = 7000000;
  7      int[] list1 = new int[SIZE];
  8      int[] list2 = new int[SIZE];
  9  
 10      for (int i = 0; i < list1.length; i++)
 11        list1[i] = list2[i] = (int)(Math.random() * 10000000);
 12  
 13      long startTime = System.currentTimeMillis();
 14      parallelMergeSort(list1); // Invoke parallel merge sort
 15      long endTime = System.currentTimeMillis();
 16      System.out.println("\nParallel time with "
 17        + Runtime.getRuntime().availableProcessors() + 
 18        " processors is " + (endTime - startTime) + " milliseconds");
 19  
 20      startTime = System.currentTimeMillis();
 21      MergeSort.mergeSort(list2); // MergeSort is in Listing 24.5
 22      endTime = System.currentTimeMillis();
 23      System.out.println("\nSequential time is " + 
 24        (endTime - startTime) + " milliseconds");
 25    }
 26  
 27    public static void parallelMergeSort(int[] list) {
 28      RecursiveAction mainTask = new SortTask(list);
 29      ForkJoinPool pool = new ForkJoinPool();
 30      pool.invoke(mainTask);
 31    }
 32  
 33    private static class SortTask extends RecursiveAction {
 34      private final int THRESHOLD = 500;
 35      private int[] list;
 36  
 37      SortTask(int[] list) {
 38        this.list = list;
 39      }
 40  
 41      @Override
 42      protected void compute() {
 43        if (list.length < THRESHOLD)
 44          java.util.Arrays.sort(list);
 45        else {
 46          // Obtain the first half
 47          int[] firstHalf = new int[list.length / 2];
 48          System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
 49  
 50          // Obtain the second half
 51          int secondHalfLength = list.length - list.length / 2;
 52          int[] secondHalf = new int[secondHalfLength];
 53          System.arraycopy(list, list.length / 2, 
 54            secondHalf, 0, secondHalfLength);
 55  
 56          // Recursively sort the two halves
 57          invokeAll(new SortTask(firstHalf), 
 58            new SortTask(secondHalf));
 59  
 60          // Merge firstHalf with secondHalf into list
 61          MergeSort.merge(firstHalf, secondHalf, list);
 62        }
 63      }
 64    }
 65  }