MULTITHREADING AND PARALLEL PROGRAMMING - Introduction to Java Programming: Comprehensive Version - page 1131

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

perform the task

sort a small list

split into two parts

// Recursively sort the two halves

57 invokeAll( new SortTask(firstHalf),

solve each part

58 new SortTask(secondHalf));

59
60 // Merge firstHalf with secondHalf into list

61 MergeSort.merge(firstHalf, secondHalf, list);

merge two parts

62 }
63 }
64 }
65 }

Parallel time with 2 processors is 2829 milliseconds
Sequential time is 4751 milliseconds

Since the sort algorithm does not return a value, we define a concrete ForkJoinTask class by
extending RecursiveAction (lines 33-64). The compute method is overridden to imple-
ment a recursive merge sort (lines 42-63). If the list is small, it is more efficient to be solved
sequentially (line 44). For a large list, it is split into two halves (lines 47-54). The two halves
are sorted concurrently (lines 57 and 58) and then merged (line 61).
The program creates a main ForkJoinTask (line 28), a ForkJoinPool (line 29), and
places the main task for execution in a ForkJoinPool (line 30). The invoke method will
return after the main task is completed.
When executing the main task, the task is split into subtasks and the subtasks are invoked
using the invokeAll method (lines 57 and 58). The invokeAll method will return after all
the subtasks are completed. Note that each subtask is further split into smaller tasks recur-
sively. Huge numbers of subtasks may be created and executed in the pool. The Fork/Join
Framework automatically executes and coordinates all the tasks efficiently.
The MergeSort class is defined in Listing 23.5. The program invokes MergeSort.merge
to merge two sorted sublists (line 61). The program also invokes MergeSort.mergeSort
(line 21) to sort a list using merge sort sequentially. You can see that the parallel sort is much
faster than the sequential sort.
Note that the loop for initializing the list can also be parallelized. However, you should
avoid using Math.random() in the code because it is synchronized and cannot be executed
in parallel (see Programming Exercise 30.12). The parallelMergeSort method only sorts