1 files changed, 137 insertions, 0 deletions
diff --git a/staging/linux-x86/sample/forkjoin/mergesort/MergeSort.java b/staging/linux-x86/sample/forkjoin/mergesort/MergeSort.java
new file mode 100644
index 0000000..0ae48dc
--- /dev/null
+++ b/staging/linux-x86/sample/forkjoin/mergesort/MergeSort.java
@@ -0,0 +1,137 @@
+/*
+ * 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();
+    }
+}