changeset 8347:10c1d69b833b

Restore Arrays to the lambda version remove duplication in Collections.
author mduigou
date Mon, 22 Apr 2013 13:55:00 -0700
parents 060cc7d29ee4
children a922c7c6b613
files src/share/classes/java/util/Arrays.java src/share/classes/java/util/Collections.java
diffstat 2 files changed, 704 insertions(+), 685 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/Arrays.java	Mon Apr 22 12:40:28 2013 -0700
+++ b/src/share/classes/java/util/Arrays.java	Mon Apr 22 13:55:00 2013 -0700
@@ -40,7 +40,6 @@
 import java.util.stream.LongStream;
 import java.util.stream.Stream;
 import java.util.stream.StreamSupport;
-import static java.util.ArraysParallelSortHelpers.*;
 
 /**
  * This class contains various methods for manipulating arrays (such as
@@ -70,17 +69,62 @@
 public class Arrays {
 
     /**
-     * The minimum array length below which the sorting algorithm will not
-     * further partition the sorting task.
+     * The minimum array length below which a parallel sorting
+     * algorithm will not further partition the sorting task. Using
+     * smaller sizes typically results in memory contention across
+     * tasks that makes parallel speedups unlikely.
      */
-    // reasonable default so that we don't overcreate tasks
-    private static final int MIN_ARRAY_SORT_GRAN = 256;
+    public static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
 
     // Suppresses default constructor, ensuring non-instantiability.
     private Arrays() {}
 
+    /**
+     * A comparator that implements the natural ordering of a group of
+     * mutually comparable elements. May be used when a supplied
+     * comparator is null. To simplify code-sharing within underlying
+     * implementations, the compare method only declares type Object
+     * for its second argument.
+     *
+     * Arrays class implementor's note: It is an empirical matter
+     * whether ComparableTimSort offers any performance benefit over
+     * TimSort used with this comparator.  If not, you are better off
+     * deleting or bypassing ComparableTimSort.  There is currently no
+     * empirical case for separating them for parallel sorting, so all
+     * public Object parallelSort methods use the same comparator
+     * based implementation.
+     */
+    static final class NaturalOrder implements Comparator<Object> {
+        @SuppressWarnings("unchecked")
+        public int compare(Object first, Object second) {
+            return ((Comparable<Object>)first).compareTo(second);
+        }
+        static final NaturalOrder INSTANCE = new NaturalOrder();
+    }
+
+    /**
+     * Checks that {@code fromIndex} and {@code toIndex} are in
+     * the range and throws an exception if they aren't.
+     */
+    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
+        if (fromIndex > toIndex) {
+            throw new IllegalArgumentException(
+                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+        }
+        if (fromIndex < 0) {
+            throw new ArrayIndexOutOfBoundsException(fromIndex);
+        }
+        if (toIndex > arrayLength) {
+            throw new ArrayIndexOutOfBoundsException(toIndex);
+        }
+    }
+
     /*
-     * Sorting of primitive type arrays.
+     * Sorting methods. Note that all public "sort" methods take the
+     * same form: Performing argument checks if necessary, and then
+     * expanding arguments into those required for the internal
+     * implementation methods residing in other package-private
+     * classes (except for legacyMergeSort, included in this class).
      */
 
     /**
@@ -95,7 +139,7 @@
      * @param a the array to be sorted
      */
     public static void sort(int[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -120,7 +164,7 @@
      */
     public static void sort(int[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
     }
 
     /**
@@ -135,7 +179,7 @@
      * @param a the array to be sorted
      */
     public static void sort(long[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -160,7 +204,7 @@
      */
     public static void sort(long[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
     }
 
     /**
@@ -175,7 +219,7 @@
      * @param a the array to be sorted
      */
     public static void sort(short[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -200,7 +244,7 @@
      */
     public static void sort(short[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
     }
 
     /**
@@ -215,7 +259,7 @@
      * @param a the array to be sorted
      */
     public static void sort(char[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -240,7 +284,7 @@
      */
     public static void sort(char[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
     }
 
     /**
@@ -255,7 +299,7 @@
      * @param a the array to be sorted
      */
     public static void sort(byte[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1);
     }
 
     /**
@@ -303,7 +347,7 @@
      * @param a the array to be sorted
      */
     public static void sort(float[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -336,7 +380,7 @@
      */
     public static void sort(float[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
     }
 
     /**
@@ -359,7 +403,7 @@
      * @param a the array to be sorted
      */
     public static void sort(double[] a) {
-        DualPivotQuicksort.sort(a);
+        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }
 
     /**
@@ -392,7 +436,637 @@
      */
     public static void sort(double[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(byte[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(byte[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1);
+        else
+            new ArraysParallelSortHelpers.FJByte.Sorter
+                (null, a, new byte[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(byte[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        else
+            new ArraysParallelSortHelpers.FJByte.Sorter
+                (null, a, new byte[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(char[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(char[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJChar.Sorter
+                (null, a, new char[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(char[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(char[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJChar.Sorter
+                (null, a, new char[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(short[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(short[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJShort.Sorter
+                (null, a, new short[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(short[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(short[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJShort.Sorter
+                (null, a, new short[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(int[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(int[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJInt.Sorter
+                (null, a, new int[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(int[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(int[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJInt.Sorter
+                (null, a, new int[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(long[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(long[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJLong.Sorter
+                (null, a, new long[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(long[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(long[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJLong.Sorter
+                (null, a, new long[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>The {@code <} relation does not provide a total order on all float
+     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+     * other value and all {@code Float.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(float[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(float[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJFloat.Sorter
+                (null, a, new float[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>The {@code <} relation does not provide a total order on all float
+     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+     * other value and all {@code Float.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(float[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(float[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJFloat.Sorter
+                (null, a, new float[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>The {@code <} relation does not provide a total order on all double
+     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+     * other value and all {@code Double.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(double[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     */
+    public static void parallelSort(double[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJDouble.Sorter
+                (null, a, new double[n], 0, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>The {@code <} relation does not provide a total order on all double
+     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+     * other value and all {@code Double.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(double[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void parallelSort(double[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJDouble.Sorter
+                (null, a, new double[n], fromIndex, n, 0,
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
+    }
+
+    /**
+     * Sorts the specified array of objects into ascending order, according
+     * to the {@linkplain Comparable natural ordering} of its elements.
+     * All elements in the array must implement the {@link Comparable}
+     * interface.  Furthermore, all elements in the array must be
+     * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
+     * not throw a {@code ClassCastException} for any elements {@code e1}
+     * and {@code e2} in the array).
+     *
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(Object[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     *
+     * @throws ClassCastException if the array contains elements that are not
+     *         <i>mutually comparable</i> (for example, strings and integers)
+     * @throws IllegalArgumentException (optional) if the natural
+     *         ordering of the array elements is found to violate the
+     *         {@link Comparable} contract
+     */
+    @SuppressWarnings("unchecked")
+    public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJObject.Sorter<T>
+                (null, a,
+                 (T[])Array.newInstance(a.getClass().getComponentType(), n),
+                 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
+    }
+
+    /**
+     * Sorts the specified range of the specified array of objects into
+     * ascending order, according to the
+     * {@linkplain Comparable natural ordering} of its
+     * elements.  The range to be sorted extends from index
+     * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
+     * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
+     * elements in this range must implement the {@link Comparable}
+     * interface.  Furthermore, all elements in this range must be <i>mutually
+     * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
+     * {@code ClassCastException} for any elements {@code e1} and
+     * {@code e2} in the array).
+     *
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * This method will cause initialization of the
+     * default {@code ForkJoinPool} if necessary.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(Object[]) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element (inclusive) to be
+     *        sorted
+     * @param toIndex the index of the last element (exclusive) to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+     *         (optional) if the natural ordering of the array elements is
+     *         found to violate the {@link Comparable} contract
+     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+     *         {@code toIndex > a.length}
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> (for example, strings and
+     *         integers).
+     */
+    @SuppressWarnings("unchecked")
+    public static <T extends Comparable<? super T>>
+    void parallelSort(T[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJObject.Sorter<T>
+                (null, a,
+                 (T[])Array.newInstance(a.getClass().getComponentType(), n),
+                 fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
+    }
+
+    /**
+     * Sorts the specified array of objects according to the order induced by
+     * the specified comparator.  All elements in the array must be
+     * <i>mutually comparable</i> by the specified comparator (that is,
+     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+     * for any elements {@code e1} and {@code e2} in the array).
+     *
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(Object[], java.util.Comparator) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param cmp the comparator to determine the order of the array.  A
+     *        {@code null} value indicates that the elements'
+     *        {@linkplain Comparable natural ordering} should be used.
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> using the specified comparator
+     * @throws IllegalArgumentException (optional) if the comparator is
+     *         found to violate the {@link java.util.Comparator} contract
+     */
+    @SuppressWarnings("unchecked")
+    public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
+        if (cmp == null)
+            cmp = NaturalOrder.INSTANCE;
+        int n = a.length, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            TimSort.sort(a, 0, n, cmp, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJObject.Sorter<T>
+                (null, a,
+                 (T[])Array.newInstance(a.getClass().getComponentType(), n),
+                 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
+    }
+
+    /**
+     * Sorts the specified range of the specified array of objects according
+     * to the order induced by the specified comparator.  The range to be
+     * sorted extends from index {@code fromIndex}, inclusive, to index
+     * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
+     * range to be sorted is empty.)  All elements in the range must be
+     * <i>mutually comparable</i> by the specified comparator (that is,
+     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+     * for any elements {@code e1} and {@code e2} in the range).
+     *
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity (currently
+     * {@value #MIN_ARRAY_SORT_GRAN}) the sub-array is sorted using the appropriate
+     * {@link Arrays#sort(Object[], int, int, java.util.Comparator) Arrays.sort} method. The algorithm
+     * requires a working space equal to the size of the original array.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element (inclusive) to be
+     *        sorted
+     * @param toIndex the index of the last element (exclusive) to be sorted
+     * @param cmp the comparator to determine the order of the array.  A
+     *        {@code null} value indicates that the elements'
+     *        {@linkplain Comparable natural ordering} should be used.
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+     *         (optional) if the natural ordering of the array elements is
+     *         found to violate the {@link Comparable} contract
+     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+     *         {@code toIndex > a.length}
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> (for example, strings and
+     *         integers).
+     */
+    @SuppressWarnings("unchecked")
+    public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
+                                        Comparator<? super T> cmp) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        if (cmp == null)
+            cmp = NaturalOrder.INSTANCE;
+        int n = toIndex - fromIndex, p, g;
+        if (n <= MIN_ARRAY_SORT_GRAN ||
+            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
+            TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
+        else
+            new ArraysParallelSortHelpers.FJObject.Sorter<T>
+                (null, a,
+                 (T[])Array.newInstance(a.getClass().getComponentType(), n),
+                 fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
     }
 
     /*
@@ -412,39 +1086,6 @@
                     "java.util.Arrays.useLegacyMergeSort")).booleanValue();
     }
 
-    /*
-     * If this platform has an optimizing VM, check whether ComparableTimSort
-     * offers any performance benefit over TimSort in conjunction with a
-     * comparator that returns:
-     *    {@code ((Comparable)first).compareTo(Second)}.
-     * If not, you are better off deleting ComparableTimSort to
-     * eliminate the code duplication.  In other words, the commented
-     * out code below is the preferable implementation for sorting
-     * arrays of Comparables if it offers sufficient performance.
-     */
-
-//    /**
-//     * A comparator that implements the natural ordering of a group of
-//     * mutually comparable elements.  Using this comparator saves us
-//     * from duplicating most of the code in this file (one version for
-//     * Comparables, one for explicit Comparators).
-//     */
-//    private static final Comparator<Object> NATURAL_ORDER =
-//            new Comparator<Object>() {
-//        @SuppressWarnings("unchecked")
-//        public int compare(Object first, Object second) {
-//            return ((Comparable<Object>)first).compareTo(second);
-//        }
-//    };
-//
-//    public static void sort(Object[] a) {
-//        sort(a, 0, a.length, NATURAL_ORDER);
-//    }
-//
-//    public static void sort(Object[] a, int fromIndex, int toIndex) {
-//        sort(a, fromIndex, toIndex, NATURAL_ORDER);
-//    }
-
     /**
      * Sorts the specified array of objects into ascending order, according
      * to the {@linkplain Comparable natural ordering} of its elements.
@@ -491,7 +1132,7 @@
         if (LegacyMergeSort.userRequested)
             legacyMergeSort(a);
         else
-            ComparableTimSort.sort(a);
+            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
     }
 
     /** To be removed in a future release. */
@@ -553,16 +1194,16 @@
      *         integers).
      */
     public static void sort(Object[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
         if (LegacyMergeSort.userRequested)
             legacyMergeSort(a, fromIndex, toIndex);
         else
-            ComparableTimSort.sort(a, fromIndex, toIndex);
+            ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
     }
 
     /** To be removed in a future release. */
     private static void legacyMergeSort(Object[] a,
                                         int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
         Object[] aux = copyOfRange(a, fromIndex, toIndex);
         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
     }
@@ -676,10 +1317,12 @@
      *         found to violate the {@link Comparator} contract
      */
     public static <T> void sort(T[] a, Comparator<? super T> c) {
+        if (c == null)
+            c = NaturalOrder.INSTANCE;
         if (LegacyMergeSort.userRequested)
             legacyMergeSort(a, c);
         else
-            TimSort.sort(a, c);
+            TimSort.sort(a, 0, a.length, c, null, 0, 0);
     }
 
     /** To be removed in a future release. */
@@ -744,16 +1387,18 @@
      */
     public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                 Comparator<? super T> c) {
+        if (c == null)
+            c = NaturalOrder.INSTANCE;
+        rangeCheck(a.length, fromIndex, toIndex);
         if (LegacyMergeSort.userRequested)
             legacyMergeSort(a, fromIndex, toIndex, c);
         else
-            TimSort.sort(a, fromIndex, toIndex, c);
+            TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
     }
 
     /** To be removed in a future release. */
     private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
                                             Comparator<? super T> c) {
-        rangeCheck(a.length, fromIndex, toIndex);
         T[] aux = copyOfRange(a, fromIndex, toIndex);
         if (c==null)
             mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
@@ -809,630 +1454,6 @@
         }
     }
 
-    /*
-     * Parallel sorting of primitive type arrays.
-     */
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(byte[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(byte[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(byte[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJByte.Sorter task = new FJByte.Sorter(a, new byte[a.length], fromIndex,
-                                               nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(char[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(char[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(char[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(char[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJChar.Sorter task = new FJChar.Sorter(a, new char[a.length], fromIndex,
-                                               nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(short[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(short[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(short[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(short[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJShort.Sorter task = new FJShort.Sorter(a, new short[a.length], fromIndex,
-                                                 nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(int[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(int[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(int[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(int[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJInt.Sorter task = new FJInt.Sorter(a, new int[a.length], fromIndex,
-                                             nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(long[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(long[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(long[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(long[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJLong.Sorter task = new FJLong.Sorter(a, new long[a.length], fromIndex,
-                                               nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>The {@code <} relation does not provide a total order on all float
-     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
-     * value compares neither less than, greater than, nor equal to any value,
-     * even itself. This method uses the total order imposed by the method
-     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
-     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
-     * other value and all {@code Float.NaN} values are considered equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(float[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(float[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>The {@code <} relation does not provide a total order on all float
-     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
-     * value compares neither less than, greater than, nor equal to any value,
-     * even itself. This method uses the total order imposed by the method
-     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
-     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
-     * other value and all {@code Float.NaN} values are considered equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(float[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(float[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJFloat.Sorter task = new FJFloat.Sorter(a, new float[a.length], fromIndex,
-                                                 nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>The {@code <} relation does not provide a total order on all double
-     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
-     * value compares neither less than, greater than, nor equal to any value,
-     * even itself. This method uses the total order imposed by the method
-     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
-     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
-     * other value and all {@code Double.NaN} values are considered equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(double[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(double[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the array into ascending order. The range
-     * to be sorted extends from the index {@code fromIndex}, inclusive, to
-     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty.
-     *
-     * <p>The {@code <} relation does not provide a total order on all double
-     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
-     * value compares neither less than, greater than, nor equal to any value,
-     * even itself. This method uses the total order imposed by the method
-     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
-     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
-     * other value and all {@code Double.NaN} values are considered equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(double[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusive, to be sorted
-     * @param toIndex the index of the last element, exclusive, to be sorted
-     *
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     *
-     * @since 1.8
-     */
-    public static void parallelSort(double[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        int gran = getSplitThreshold(nelements);
-        FJDouble.Sorter task = new FJDouble.Sorter(a, new double[a.length],
-                                                   fromIndex, nelements, gran);
-        task.invoke();
-    }
-
-    /*
-     * Parallel sorting of complex type arrays.
-     */
-
-    /**
-     * Sorts the specified array of objects into ascending order, according
-     * to the {@linkplain Comparable natural ordering} of its elements.
-     * All elements in the array must implement the {@link Comparable}
-     * interface.  Furthermore, all elements in the array must be
-     * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
-     * not throw a {@code ClassCastException} for any elements {@code e1}
-     * and {@code e2} in the array).
-     *
-     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
-     * may be reordered as a result of the sort.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     *
-     * @throws ClassCastException if the array contains elements that are not
-     *         <i>mutually comparable</i> (for example, strings and integers)
-     * @throws IllegalArgumentException (optional) if the natural
-     *         ordering of the array elements is found to violate the
-     *         {@link Comparable} contract
-     *
-     * @since 1.8
-     */
-    public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
-        parallelSort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the specified array of objects into
-     * ascending order, according to the
-     * {@linkplain Comparable natural ordering} of its
-     * elements.  The range to be sorted extends from index
-     * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
-     * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
-     * elements in this range must implement the {@link Comparable}
-     * interface.  Furthermore, all elements in this range must be <i>mutually
-     * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
-     * {@code ClassCastException} for any elements {@code e1} and
-     * {@code e2} in the array).
-     *
-     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
-     * may be reordered as a result of the sort.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
-     *         (optional) if the natural ordering of the array elements is
-     *         found to violate the {@link Comparable} contract
-     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
-     *         {@code toIndex > a.length}
-     * @throws ClassCastException if the array contains elements that are
-     *         not <i>mutually comparable</i> (for example, strings and
-     *         integers).
-     *
-     * @since 1.8
-     */
-    public static <T extends Comparable<? super T>>
-            void parallelSort(T[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        Class<?> tc = a.getClass().getComponentType();
-        @SuppressWarnings("unchecked")
-        T[] workspace = (T[])Array.newInstance(tc, a.length);
-        int gran = getSplitThreshold(nelements);
-        FJComparable.Sorter<T> task = new FJComparable.Sorter<>(a, workspace,
-                                                                fromIndex,
-                                                                nelements, gran);
-        task.invoke();
-    }
-
-    /**
-     * Sorts the specified array of objects according to the order induced by
-     * the specified comparator.  All elements in the array must be
-     * <i>mutually comparable</i> by the specified comparator (that is,
-     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
-     * for any elements {@code e1} and {@code e2} in the array).
-     *
-     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
-     * may be reordered as a result of the sort.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param c the comparator to determine the order of the array.  A
-     *        {@code null} value indicates that the elements'
-     *        {@linkplain Comparable natural ordering} should be used.
-     * @throws ClassCastException if the array contains elements that are
-     *         not <i>mutually comparable</i> using the specified comparator
-     * @throws IllegalArgumentException (optional) if the comparator is
-     *         found to violate the {@link java.util.Comparator} contract
-     *
-     * @since 1.8
-     */
-    public static <T> void parallelSort(T[] a, Comparator<? super T> c) {
-        parallelSort(a, 0, a.length, c);
-    }
-
-    /**
-     * Sorts the specified range of the specified array of objects according
-     * to the order induced by the specified comparator.  The range to be
-     * sorted extends from index {@code fromIndex}, inclusive, to index
-     * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
-     * range to be sorted is empty.)  All elements in the range must be
-     * <i>mutually comparable</i> by the specified comparator (that is,
-     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
-     * for any elements {@code e1} and {@code e2} in the range).
-     *
-     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
-     * may be reordered as a result of the sort.
-     *
-     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
-     * that breaks the array into sub-arrays that are themselves sorted and then
-     * merged. When the sub-array length reaches a minimum granularity, the
-     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
-     * Arrays.sort} method. The algorithm requires a working space equal to the
-     * size of the original array. The {@link
-     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
-     * used to execute any parallel tasks.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element (inclusive) to be
-     *        sorted
-     * @param toIndex the index of the last element (exclusive) to be sorted
-     * @param c the comparator to determine the order of the array.  A
-     *        {@code null} value indicates that the elements'
-     *        {@linkplain Comparable natural ordering} should be used.
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
-     *         (optional) if the natural ordering of the array elements is
-     *         found to violate the {@link Comparable} contract
-     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
-     *         {@code toIndex > a.length}
-     * @throws ClassCastException if the array contains elements that are
-     *         not <i>mutually comparable</i> (for example, strings and
-     *         integers).
-     *
-     * @since 1.8
-     */
-    public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
-                                        Comparator<? super T> c) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        int nelements = toIndex - fromIndex;
-        Class<?> tc = a.getClass().getComponentType();
-        @SuppressWarnings("unchecked")
-        T[] workspace = (T[])Array.newInstance(tc, a.length);
-        int gran = getSplitThreshold(nelements);
-        FJComparator.Sorter<T> task = new FJComparator.Sorter<>(a, workspace,
-                                                                fromIndex,
-                                                                nelements, gran, c);
-        task.invoke();
-    }
-
-    /**
-     * Returns the size threshold for splitting into subtasks.
-     * By default, uses about 8 times as many tasks as threads
-     *
-     * @param n number of elements in the array to be processed
-     */
-    private static int getSplitThreshold(int n) {
-        int p = java.util.concurrent.ForkJoinPool.getCommonPoolParallelism();
-        int t = (p > 1) ? (1 + n / (p << 3)) : n;
-        return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;
-    }
-
-    /**
-     * Checks that {@code fromIndex} and {@code toIndex} are in
-     * the range and throws an appropriate exception, if they aren't.
-     */
-    private static void rangeCheck(int length, int fromIndex, int toIndex) {
-        if (fromIndex > toIndex) {
-            throw new IllegalArgumentException(
-                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
-        }
-        if (fromIndex < 0) {
-            throw new ArrayIndexOutOfBoundsException(fromIndex);
-        }
-        if (toIndex > length) {
-            throw new ArrayIndexOutOfBoundsException(toIndex);
-        }
-    }
-
     // Parallel prefix
 
     /**
@@ -4490,6 +4511,7 @@
         dejaVu.remove(a);
     }
 
+
     /**
      * Set all elements of the specified array, using the provided
      * generator function to compute each element.
--- a/src/share/classes/java/util/Collections.java	Mon Apr 22 12:40:28 2013 -0700
+++ b/src/share/classes/java/util/Collections.java	Mon Apr 22 13:55:00 2013 -0700
@@ -4754,12 +4754,9 @@
         @Override
         public void forEach(Consumer<? super E> action) {q.forEach(action);}
         @Override
-        public Spliterator<E> spliterator() {return q.spliterator();}
-        @Override
         public boolean removeIf(Predicate<? super E> filter) {
             return q.removeIf(filter);
         }
-
         @Override
         public Spliterator<E> spliterator() {return q.spliterator();}
         @Override