1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
/*
* Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* - Neither the name of Oracle nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveAction;
/**
* A class for sorting an array of {@code ints} in parallel.
* A {@code ForkJoinPool} is used for the parallelism, using the merge sort
* algorithm the array is split into halves and a new sub task is created
* for each part. Each sub task is dispatched to the {@code ForkJoinPool}
* which will schedule the task to a {@code Thread}.
* This happens until the size of the array is at most 2
* elements long. At this point the array is sorted using a simple compare
* and possibly a swap. The tasks then finish by using insert sort to
* merge the two just sorted arrays.
*
* The idea of this class is to demonstrate the usage of RecursiveAction not
* to implement the best possible parallel merge sort. This version creates
* a small array for each merge (creating a lot of objects), this could
* be avoided by keeping a single array.
*/
public class MergeSort {
private final ForkJoinPool pool;
private static class MergeSortTask extends RecursiveAction {
private final int[] array;
private final int low;
private final int high;
private static final int THRESHOLD = 8;
/**
* Creates a {@code MergeSortTask} containing the array and the bounds of the array
*
* @param array the array to sort
* @param low the lower element to start sorting at
* @param high the non-inclusive high element to sort to
*/
protected MergeSortTask(int[] array, int low, int high) {
this.array = array;
this.low = low;
this.high = high;
}
@Override
protected void compute() {
if (high - low <= THRESHOLD) {
Arrays.sort(array, low, high);
} else {
int middle = low + ((high - low) >> 1);
// Execute the sub tasks and wait for them to finish
invokeAll(new MergeSortTask(array, low, middle), new MergeSortTask(array, middle, high));
// Then merge the results
merge(middle);
}
}
/**
* Merges the two sorted arrays this.low, middle - 1 and middle, this.high - 1
* @param middle the index in the array where the second sorted list begins
*/
private void merge(int middle) {
if (array[middle - 1] < array[middle]) {
return; // the arrays are already correctly sorted, so we can skip the merge
}
int[] copy = new int[high - low];
System.arraycopy(array, low, copy, 0, copy.length);
int copyLow = 0;
int copyHigh = high - low;
int copyMiddle = middle - low;
for (int i = low, p = copyLow, q = copyMiddle; i < high; i++) {
if (q >= copyHigh || (p < copyMiddle && copy[p] < copy[q]) ) {
array[i] = copy[p++];
} else {
array[i] = copy[q++];
}
}
}
}
/**
* Creates a {@code MergeSort} containing a ForkJoinPool with the indicated parallelism level
* @param parallelism the parallelism level used
*/
public MergeSort(int parallelism) {
pool = new ForkJoinPool(parallelism);
}
/**
* Sorts all the elements of the given array using the ForkJoin framework
* @param array the array to sort
*/
public void sort(int[] array) {
ForkJoinTask<Void> job = pool.submit(new MergeSortTask(array, 0, array.length));
job.join();
}
}
|
