| /* |
| * 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. |
| */ |
| |
| /* |
| * This source code is provided to illustrate the usage of a given feature |
| * or technique and has been deliberately simplified. Additional steps |
| * required for a production-quality application, such as security checks, |
| * input validation and proper error handling, might not be present in |
| * this sample code. |
| */ |
| |
| |
| 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(); |
| } |
| } |