changeset 7837:0309ea20fc21

Improvements to array sorting. Contributed-by: Doug Lea <dl@cs.oswego.edu>
author psandoz
date Mon, 08 Apr 2013 16:05:54 +0200
parents 4adff1640806
children 526131346981
files src/share/classes/java/util/Arrays.java src/share/classes/java/util/ArraysParallelSortHelpers.java src/share/classes/java/util/ComparableTimSort.java src/share/classes/java/util/DualPivotQuicksort.java src/share/classes/java/util/TimSort.java
diffstat 5 files changed, 890 insertions(+), 920 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/Arrays.java	Mon Apr 08 15:42:32 2013 +0200
+++ b/src/share/classes/java/util/Arrays.java	Mon Apr 08 16:05:54 2013 +0200
@@ -74,13 +74,57 @@
      * smaller sizes typically results in memory contention across
      * tasks that makes parallel speedups unlikely.
      */
-    public static final int MIN_ARRAY_SORT_GRAN = 1 << 13; 
+    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,7 @@
      */
     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);
     }
 
     /**
@@ -408,7 +452,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(byte[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -433,17 +485,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
+        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 {
-            int g = n / (p << 3);
+        else
             new ArraysParallelSortHelpers.FJByte.Sorter
                 (null, a, new byte[n], fromIndex, n, 0,
-                 (g <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -459,7 +510,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(char[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -484,17 +543,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(char[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -510,7 +568,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(short[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -535,17 +601,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(short[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -561,7 +626,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(int[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -586,17 +659,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(int[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -612,7 +684,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(long[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -637,17 +717,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(long[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -671,7 +750,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(float[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -704,17 +791,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(float[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -738,7 +824,15 @@
      * @param a the array to be sorted
      */
     public static void parallelSort(double[] a) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -771,17 +865,16 @@
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void parallelSort(double[] a, int fromIndex, int toIndex) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-        else {
-            int g = n / (p << 3);
+        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 <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
+                 MIN_ARRAY_SORT_GRAN : g).invoke();
     }
 
     /**
@@ -811,8 +904,18 @@
      *         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) {
-        parallelSort(a, 0, a.length);
+        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();
     }
 
     /**
@@ -854,23 +957,20 @@
      *         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) {
-        checkFromToBounds(a.length, fromIndex, toIndex);
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            ComparableTimSort.sort(a, fromIndex, toIndex);
-        else {
-            int g = n / (p << 3);
-            Class<?> tc = a.getClass().getComponentType();
-            @SuppressWarnings("unchecked")
-            T[] ws = (T[])Array.newInstance(tc, n);
-            new ArraysParallelSortHelpers.FJComparable.Sorter<>
-                (null, a, ws, fromIndex, n, 0, 
-                 (g <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke();
-        }
+        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();
     }
 
     /**
@@ -899,8 +999,20 @@
      * @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) {
-        parallelSort(a, 0, a.length, 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();
     }
 
     /**
@@ -939,22 +1051,22 @@
      *         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) {
-        int n = toIndex - fromIndex;
-        int p = ForkJoinPool.getCommonPoolParallelism();
-        if (p == 1 || n <= MIN_ARRAY_SORT_GRAN)
-            TimSort.sort(a, fromIndex, toIndex, cmp);
-        else {
-            int g = n / (p << 3);
-            Class<?> tc = a.getClass().getComponentType();
-            @SuppressWarnings("unchecked")
-                T[] ws = (T[])Array.newInstance(tc, n);
-            new ArraysParallelSortHelpers.FJComparator.Sorter<>
-                (null, a, ws, fromIndex, n, 0,
-                 (g <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g,
-                 cmp).invoke();
-        }
+        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();
     }
 
     /*
@@ -974,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.
@@ -1053,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. */
@@ -1115,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);
     }
@@ -1238,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. */
@@ -1306,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);
@@ -1371,23 +1454,6 @@
         }
     }
 
-    /**
-     * 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
 
     /**
@@ -1426,7 +1492,7 @@
      */
     public static <T> void parallelPrefix(T[] array, int fromIndex,
                                           int toIndex, BinaryOperator<T> op) {
-        checkFromToBounds(array.length, fromIndex, toIndex);
+        rangeCheck(array.length, fromIndex, toIndex);
         if (fromIndex < toIndex)
             new ArrayPrefixHelpers.CumulateTask<>
                     (null, op, array, fromIndex, toIndex).invoke();
@@ -1468,7 +1534,7 @@
      */
     public static void parallelPrefix(long[] array, int fromIndex,
                                       int toIndex, LongBinaryOperator op) {
-        checkFromToBounds(array.length, fromIndex, toIndex);
+        rangeCheck(array.length, fromIndex, toIndex);
         if (fromIndex < toIndex)
             new ArrayPrefixHelpers.LongCumulateTask
                     (null, op, array, fromIndex, toIndex).invoke();
@@ -1510,7 +1576,7 @@
      */
     public static void parallelPrefix(double[] array, int fromIndex,
                                       int toIndex, DoubleBinaryOperator op) {
-        checkFromToBounds(array.length, fromIndex, toIndex);
+        rangeCheck(array.length, fromIndex, toIndex);
         if (fromIndex < toIndex)
             new ArrayPrefixHelpers.DoubleCumulateTask
                     (null, op, array, fromIndex, toIndex).invoke();
@@ -1552,7 +1618,7 @@
      */
     public static void parallelPrefix(int[] array, int fromIndex,
                                       int toIndex, IntBinaryOperator op) {
-        checkFromToBounds(array.length, fromIndex, toIndex);
+        rangeCheck(array.length, fromIndex, toIndex);
         if (fromIndex < toIndex)
             new ArrayPrefixHelpers.IntCumulateTask
                     (null, op, array, fromIndex, toIndex).invoke();
@@ -4561,23 +4627,6 @@
     }
 
     /**
-     * Checks that {@code fromIndex} and {@code toIndex} are in
-     * the range and throws an exception if they aren't.
-     */
-    private static void checkFromToBounds(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);
-        }
-    }
-
-    /**
      * Creates a {@link Spliterator} covering all of the specified array.
      *
      * <p>The spliterator reports {@link Spliterator#SIZED},
--- a/src/share/classes/java/util/ArraysParallelSortHelpers.java	Mon Apr 08 15:42:32 2013 +0200
+++ b/src/share/classes/java/util/ArraysParallelSortHelpers.java	Mon Apr 08 16:05:54 2013 +0200
@@ -50,36 +50,36 @@
  * (workspace and main swap roles on each subsort step.)  Leaf-level
  * sorts use the associated sequential sort.
  *
- * Merger classes perform merging for Sorter. If big enough, it splits
- * the Left partition in half; finds the greatest point in Right
- * partition less than the beginning of the second half of Left via
- * binary search; and then, in parallel, merges left half of Left with
- * elements of Right up to split point, and merges right half of Left
- * with elements of R past split point. At leaf, it just sequentially
- * merges. The Mergers also include checks for excessive imbalances
- * (hardwired to stop if less than threshold/8 elements on either
- * side) and adjust for duplicate key runs on each side by placing
- * merge bounds at the beginnings of runs. This is necessary to
- * maintain sort-stability in the Object versions, and further helps
- * avoid imbalances in others.
+ * Merger classes perform merging for Sorter.  They are structured
+ * such that if the underlying sort is stable (as is true for
+ * TimSort), then so is the full sort.  If big enough, they split the
+ * largest of the two partitions in half, find the greatest point in
+ * smaller partition less than the beginning of the second half of
+ * larger via binary search; and then merge in parallel the two
+ * partitions.  In part to ensure tasks are triggered in
+ * stability-preserving order, the current CountedCompleter design
+ * requires some little tasks to serve as place holders for triggering
+ * completion tasks.  These classes (EmptyCompleter and Relay) don't
+ * need to keep track of the arrays, and are never themselves forked,
+ * so don't hold any task state.
  *
- * The current CountedCompleter design also requires some little tasks
- * to serve as place holders for triggering the merges and re-merges.
- * These classes (EmptyCompleter and Relay) don't need to keep track
- * of the arrays, and are never themselves forked, so don't hold any
- * task state.
+ * The primitive class versions (FJByte... FJDouble) are
+ * identical to each other except for type declarations.
+ *
+ * The base sequential sorts rely on non-public versions of TimSort,
+ * ComparableTimSort, and DualPivotQuicksort sort methods that accept
+ * temp workspace array slices that we will have already allocated, so
+ * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
+ * sort, that does not ever use a workspace array.)
  */
 /*package*/ class ArraysParallelSortHelpers {
 
     /*
-     * The primitive class versions (FJByte... FJDouble) classes are
-     * identical to FJComparable version, except removing task class
-     * parameter, replacing T with type, and replacing a.compareTo(b)
-     * with a relop b.
-     *
-     * The task classes have a lot of parameters, that are copied to
-     * local variables and used in compute() methods, We place these
-     * in as few lines as possible to minimize distraction.
+     * Style note: The task classes have a lot of parameters, that are
+     * stored as task fields and copied to local variables and used in
+     * compute() methods, We pack these into as few lines as possible,
+     * and hoist consistency checks among them before main loops, to
+     * reduce distraction.
      */
 
     /**
@@ -108,120 +108,8 @@
         }
     }
 
-    /** Comparable support class */
-    static final class FJComparable {
-        static final class Sorter<T extends Comparable<? super T>>
-            extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final T[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
-                   int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                T[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
-                    n = q;
-                    Relay fc = new Relay(new Merger<>(s,  w, a, wb,  h,
-                                                      whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger<>(fc, a, w, hb, q,
-                                                      ub, un, whb, g));
-                    Relay bc = new Relay(new Merger<>(fc, a, w, b,  q,
-                                                      qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter<T> su = new Sorter<>(rc, a, w, ub, un, wub, g);
-                    Sorter<T> sh = new Sorter<>(rc, a, w, hb, q,  whb, g);
-                    Sorter<T> sq = new Sorter<>(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
-                }
-                ComparableTimSort.sort(a, b, b + n, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger<T extends Comparable<? super T>>
-            extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final T[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, T[] a, T[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                T[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    T split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split.compareTo(a[rb + rm]) <= 0)
-                            rh = rm;
-                        else
-                            rl = rm + 1;
-                    }
-                    int s, sl, sr;
-                    while (rh > eighth && split.compareTo(a[rb + rh - 1]) == 0)
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split.compareTo(a[lb + lh - 1]) == 0)
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger<>(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                                 g).fork();
-                    rn = rh;
-                    ln = lh;
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    T t, al, ar;
-                    if ((al = a[lb]).compareTo(ar = a[rb]) <= 0) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-
-                tryComplete();
-            }
-        }
-
-    } // FJComparable
-
     /** Object + Comparator support class */
-    static final class FJComparator {
+    static final class FJObject {
         static final class Sorter<T> extends CountedCompleter<Void> {
             static final long serialVersionUID = 2446542900576103244L;
             final T[] a, w;
@@ -241,24 +129,18 @@
                 T[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger<T>(s, w, a, wb, h,
+                                                       wb+h, n-h, b, g, c));
+                    Relay rc = new Relay(new Merger<T>(fc, a, w, b+h, q,
+                                                       b+u, n-u, wb+h, g, c));
+                    new Sorter<T>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
+                    new Sorter<T>(rc, a, w, b+h, q, wb+h, g, c).fork();;
+                    Relay bc = new Relay(new Merger<T>(fc, a, w, b, q,
+                                                       b+q, h-q, wb, g, c));
+                    new Sorter<T>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger<>(s,  w, a, wb,  h,
-                                                      whb, hn, b,  g, c));
-                    Relay rc = new Relay(new Merger<>(fc, a, w, hb, q,
-                                                      ub, un, whb, g, c));
-                    Relay bc = new Relay(new Merger<>(fc, a, w, b,  q,
-                                                      qb, hq, wb,  g, c));
-                    s = new EmptyCompleter(bc);
-                    Sorter<T> su = new Sorter<>(rc, a, w, ub, un, wub, g, c);
-                    Sorter<T> sh = new Sorter<>(rc, a, w, hb, q,  whb, g, c);
-                    Sorter<T> sq = new Sorter<>(bc, a, w, qb, hq, wqb, g, c);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
                 TimSort.sort(a, b, b + n, c, w, wb, n);
                 s.tryComplete();
@@ -287,33 +169,43 @@
                 T[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    T split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (c.compare(split, a[rb + rm]) <= 0)
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
+                    c == null)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        T split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (c.compare(split, a[rm + rb]) <= 0)
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && c.compare(split, a[rb + rh - 1]) == 0)
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && c.compare(split, a[lb + lh - 1]) == 0)
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger<>(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                                 g, c).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        T split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (c.compare(split, a[lm + lb]) <= 0)
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger<T> m = new Merger<T>(this, a, w, lb + lh, ln - lh,
+                                                rb + rh, rn - rh,
+                                                k + lh + rh, g, c);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -334,8 +226,9 @@
 
                 tryComplete();
             }
+
         }
-    } // FJComparator
+    } // FJObject
 
     /** byte support class */
     static final class FJByte {
@@ -343,8 +236,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final byte[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -354,24 +247,18 @@
                 byte[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
                 DualPivotQuicksort.sort(a, b, b + n - 1);
                 s.tryComplete();
@@ -396,33 +283,42 @@
                 byte[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    byte split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        byte split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        byte split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -440,7 +336,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
@@ -452,8 +347,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final char[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, char[] a, char[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -463,26 +358,20 @@
                 char[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -505,33 +394,42 @@
                 char[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    char split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        char split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        char split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -549,11 +447,9 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
-
     } // FJChar
 
     /** short support class */
@@ -562,8 +458,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final short[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, short[] a, short[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -573,26 +469,20 @@
                 short[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -615,33 +505,42 @@
                 short[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    short split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        short split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        short split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -659,7 +558,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
@@ -671,8 +569,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final int[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, int[] a, int[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -682,26 +580,20 @@
                 int[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -724,33 +616,42 @@
                 int[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    int split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        int split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        int split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -768,7 +669,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
@@ -780,8 +680,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final long[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, long[] a, long[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -791,26 +691,20 @@
                 long[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -833,33 +727,42 @@
                 long[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    long split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        long split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        long split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -877,7 +780,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
@@ -889,8 +791,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final float[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, float[] a, float[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -900,26 +802,20 @@
                 float[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -942,33 +838,42 @@
                 float[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    float split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        float split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        float split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -986,7 +891,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
@@ -998,8 +902,8 @@
             static final long serialVersionUID = 2446542900576103244L;
             final double[] a, w;
             final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, double[] a, double[] w, int base, int size,
-                   int wbase, int gran) {
+            Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
+                   int size, int wbase, int gran) {
                 super(par);
                 this.a = a; this.w = w; this.base = base; this.size = size;
                 this.wbase = wbase; this.gran = gran;
@@ -1009,26 +913,20 @@
                 double[] a = this.a, w = this.w; // localize all params
                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
                 while (n > g) {
-                    int h = n >>> 1, q = n >>> 2, u = h + q; // quartiles
-                    int qb = b + q, hb = b + h, ub = b + u;  // bases
-                    int wqb = wb + q, whb = wb + h, wub = wb + u;
-                    int hq = h - q, hn = n - h, un = n - u;  // sizes
+                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
+                                                    wb+h, n-h, b, g));
+                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+                                                    b+u, n-u, wb+h, g));
+                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
+                                                    b+q, h-q, wb, g));
+                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+                    s = new EmptyCompleter(bc);
                     n = q;
-                    Relay fc = new Relay(new Merger(s,  w, a, wb,  h,
-                                                    whb, hn, b,  g));
-                    Relay rc = new Relay(new Merger(fc, a, w, hb, q,
-                                                    ub, un, whb, g));
-                    Relay bc = new Relay(new Merger(fc, a, w, b,  q,
-                                                    qb, hq, wb,  g));
-                    s = new EmptyCompleter(bc);
-                    Sorter su = new Sorter(rc, a, w, ub, un, wub, g);
-                    Sorter sh = new Sorter(rc, a, w, hb, q,  whb, g);
-                    Sorter sq = new Sorter(bc, a, w, qb, hq, wqb, g);
-                    su.fork();
-                    sh.fork();
-                    sq.fork();
                 }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
+                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
                 s.tryComplete();
             }
         }
@@ -1051,33 +949,42 @@
                 double[] a = this.a, w = this.w; // localize all params
                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
                     rn = this.rsize, k = this.wbase, g = this.gran;
-                int eighth = g >>> 3;
-                for (;;) {
-                    int lh = ln >>> 1;
-                    double split = a[lb + lh];
-                    int rh = rn;
-                    for (int rl = 0; rl < rh;) {
-                        int rm = (rl + rh) >>> 1;
-                        if (split <= a[rb + rm])
-                            rh = rm;
-                        else
-                            rl = rm + 1;
+                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+                    throw new IllegalStateException(); // hoist checks
+                for (int lh, rh;;) {  // split larger, find point in smaller
+                    if (ln >= rn) {
+                        if (ln <= g)
+                            break;
+                        rh = rn;
+                        double split = a[(lh = ln >>> 1) + lb];
+                        for (int lo = 0; lo < rh; ) {
+                            int rm = (lo + rh) >>> 1;
+                            if (split <= a[rm + rb])
+                                rh = rm;
+                            else
+                                lo = rm + 1;
+                        }
                     }
-                    int s, sl, sr;
-                    while (rh > eighth && split == a[rb + rh - 1])
-                        --rh; // back up right to beginning of run
-                    if (rh <= eighth)
-                        break; // too imbalanced
-                    while (lh > eighth && split == a[lb + lh - 1])
-                        --lh; // back up left
-                    if (lh <= eighth || (s = lh + rh) <= g || // left too small
-                        (sl = ln - lh) + (sr = rn - rh) <= g) // right too small
-                        break;
-                    addToPendingCount(1);
-                    new Merger(this, a, w, lb + lh, sl, rb + rh, sr, k + s,
-                               g).fork();
+                    else {
+                        if (rn <= g)
+                            break;
+                        lh = ln;
+                        double split = a[(rh = rn >>> 1) + rb];
+                        for (int lo = 0; lo < lh; ) {
+                            int lm = (lo + lh) >>> 1;
+                            if (split <= a[lm + lb])
+                                lh = lm;
+                            else
+                                lo = lm + 1;
+                        }
+                    }
+                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+                                          rb + rh, rn - rh,
+                                          k + lh + rh, g);
                     rn = rh;
                     ln = lh;
+                    addToPendingCount(1);
+                    m.fork();
                 }
 
                 int lf = lb + ln, rf = rb + rn; // index bounds
@@ -1095,7 +1002,6 @@
                     System.arraycopy(a, rb, w, k, rf - rb);
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
-
                 tryComplete();
             }
         }
--- a/src/share/classes/java/util/ComparableTimSort.java	Mon Apr 08 15:42:32 2013 +0200
+++ b/src/share/classes/java/util/ComparableTimSort.java	Mon Apr 08 16:05:54 2013 +0200
@@ -123,7 +123,7 @@
         int len = a.length;
         int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
             len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
-        if (work == null || workLen < tlen) {
+        if (work == null || workLen < tlen || workBase + tlen > work.length) {
             tmp = new Object[tlen];
             tmpBase = 0;
             tmpLen = tlen;
@@ -152,26 +152,28 @@
     }
 
     /*
-     * The next three methods (which are package private and static) constitute
-     * the entire API of this class.  Each of these methods obeys the contract
-     * of the public method with the same signature in java.util.Arrays.
+     * The next method (package private and static) constitutes the
+     * entire API of this class. 
      */
 
-    static void sort(Object[] a) {
-        sort(a, 0, a.length, null, 0, 0);
-    }
-
-    static void sort(Object[] a, int lo, int hi) {
-        sort(a, lo, hi, null, 0, 0);
-    }
-
     /**
-     * sort, using the given workspace array slice for temp storage
-     * when possible.
+     * Sorts the given range, using the given workspace array slice
+     * for temp storage when possible. This method is designed to be
+     * invoked from public methods (in class Arrays) after performing
+     * any necessary array bounds checks and expanding parameters into
+     * the required forms.
+     *
+     * @param a the array to be sorted
+     * @param lo the index of the first element, inclusive, to be sorted
+     * @param hi the index of the last element, exclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      * @since 1.8
      */
     static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
-        rangeCheck(a.length, lo, hi);
+        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
+
         int nRemaining  = hi - lo;
         if (nRemaining < 2)
             return;  // Arrays of size 0 and 1 are always sorted
@@ -898,24 +900,4 @@
         return tmp;
     }
 
-    /**
-     * Checks that fromIndex and toIndex are in range, and throws an
-     * appropriate exception if they aren't.
-     *
-     * @param arrayLen the length of the array
-     * @param fromIndex the index of the first element of the range
-     * @param toIndex the index after the last element of the range
-     * @throws IllegalArgumentException if fromIndex > toIndex
-     * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
-     *         or toIndex > arrayLen
-     */
-    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
-        if (fromIndex > toIndex)
-            throw new IllegalArgumentException("fromIndex(" + fromIndex +
-                       ") > toIndex(" + toIndex+")");
-        if (fromIndex < 0)
-            throw new ArrayIndexOutOfBoundsException(fromIndex);
-        if (toIndex > arrayLen)
-            throw new ArrayIndexOutOfBoundsException(toIndex);
-    }
 }
--- a/src/share/classes/java/util/DualPivotQuicksort.java	Mon Apr 08 15:42:32 2013 +0200
+++ b/src/share/classes/java/util/DualPivotQuicksort.java	Mon Apr 08 16:05:54 2013 +0200
@@ -32,6 +32,11 @@
  * quicksorts to degrade to quadratic performance, and is typically
  * faster than traditional (one-pivot) Quicksort implementations.
  *
+ * All exposed methods are package-private, designed to be invoked
+ * from public methods (in class Arrays) after performing any
+ * necessary array bounds checks and expanding parameters into the
+ * required forms.
+ *
  * @author Vladimir Yaroslavskiy
  * @author Jon Bentley
  * @author Josh Bloch
@@ -89,22 +94,18 @@
      */
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(int[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(int[] a, int left, int right) {
+    static void sort(int[] a, int left, int right, 
+                     int[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -147,24 +148,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        int[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        int[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new int[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new int[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new int[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -172,17 +184,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
@@ -529,22 +541,18 @@
     }
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(long[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(long[] a, int left, int right) {
+    static void sort(long[] a, int left, int right,
+                     long[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -587,24 +595,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        long[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        long[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new long[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new long[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new long[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -612,17 +631,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
@@ -969,22 +988,18 @@
     }
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(short[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(short[] a, int left, int right) {
+    static void sort(short[] a, int left, int right,
+                     short[] work, int workBase, int workLen) {
         // Use counting sort on large arrays
         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             int[] count = new int[NUM_SHORT_VALUES];
@@ -1002,7 +1017,7 @@
                 } while (--s > 0);
             }
         } else { // Use Dual-Pivot Quicksort on small arrays
-            doSort(a, left, right);
+            doSort(a, left, right, work, workBase, workLen);
         }
     }
 
@@ -1015,8 +1030,12 @@
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    private static void doSort(short[] a, int left, int right) {
+    private static void doSort(short[] a, int left, int right,
+                               short[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -1059,24 +1078,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        short[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        short[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new short[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new short[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new short[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -1084,17 +1114,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
@@ -1441,22 +1471,18 @@
     }
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(char[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(char[] a, int left, int right) {
+    static void sort(char[] a, int left, int right,
+                     char[] work, int workBase, int workLen) {
         // Use counting sort on large arrays
         if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             int[] count = new int[NUM_CHAR_VALUES];
@@ -1474,7 +1500,7 @@
                 } while (--s > 0);
             }
         } else { // Use Dual-Pivot Quicksort on small arrays
-            doSort(a, left, right);
+            doSort(a, left, right, work, workBase, workLen);
         }
     }
 
@@ -1487,8 +1513,12 @@
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    private static void doSort(char[] a, int left, int right) {
+    private static void doSort(char[] a, int left, int right,
+                               char[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -1531,24 +1561,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        char[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        char[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new char[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new char[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new char[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -1556,17 +1597,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
@@ -1916,22 +1957,13 @@
     private static final int NUM_BYTE_VALUES = 1 << 8;
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(byte[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
      * Sorts the specified range of the array.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
      */
-    public static void sort(byte[] a, int left, int right) {
+    static void sort(byte[] a, int left, int right) {
         // Use counting sort on large arrays
         if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
             int[] count = new int[NUM_BYTE_VALUES];
@@ -1963,22 +1995,18 @@
     }
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(float[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(float[] a, int left, int right) {
+    static void sort(float[] a, int left, int right,
+                     float[] work, int workBase, int workLen) {
         /*
          * Phase 1: Move NaNs to the end of the array.
          */
@@ -1997,7 +2025,7 @@
         /*
          * Phase 2: Sort everything except NaNs (which are already in place).
          */
-        doSort(a, left, right);
+        doSort(a, left, right, work, workBase, workLen);
 
         /*
          * Phase 3: Place negative zeros before positive zeros.
@@ -2064,8 +2092,12 @@
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    private static void doSort(float[] a, int left, int right) {
+    private static void doSort(float[] a, int left, int right,
+                               float[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -2108,24 +2140,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        float[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        float[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new float[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new float[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new float[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -2133,17 +2176,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
@@ -2490,22 +2533,18 @@
     }
 
     /**
-     * Sorts the specified array.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(double[] a) {
-        sort(a, 0, a.length - 1);
-    }
-
-    /**
-     * Sorts the specified range of the array.
+     * Sorts the specified range of the array using the given
+     * workspace array slice if possible for merging
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    public static void sort(double[] a, int left, int right) {
+    static void sort(double[] a, int left, int right,
+                     double[] work, int workBase, int workLen) {
         /*
          * Phase 1: Move NaNs to the end of the array.
          */
@@ -2524,7 +2563,7 @@
         /*
          * Phase 2: Sort everything except NaNs (which are already in place).
          */
-        doSort(a, left, right);
+        doSort(a, left, right, work, workBase, workLen);
 
         /*
          * Phase 3: Place negative zeros before positive zeros.
@@ -2591,8 +2630,12 @@
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      */
-    private static void doSort(double[] a, int left, int right) {
+    private static void doSort(double[] a, int left, int right,
+                               double[] work, int workBase, int workLen) {
         // Use Quicksort on small arrays
         if (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right, true);
@@ -2635,24 +2678,35 @@
         }
 
         // Check special cases
+        // Implementation note: variable "right" is increased by 1.
         if (run[count] == right++) { // The last run contains one element
             run[++count] = right;
         } else if (count == 1) { // The array is already sorted
             return;
         }
 
-        /*
-         * Create temporary array, which is used for merging.
-         * Implementation note: variable "right" is increased by 1.
-         */
-        double[] b; byte odd = 0;
+        // Determine alternation base for merge
+        byte odd = 0;
         for (int n = 1; (n <<= 1) < count; odd ^= 1);
 
+        // Use or create temporary array b for merging
+        double[] b;                 // temp array; alternates with a
+        int ao, bo;              // array offsets from 'left'
+        int blen = right - left; // space needed for b
+        if (work == null || workLen < blen || workBase + blen > work.length) {
+            work = new double[blen];
+            workBase = 0;
+        }
         if (odd == 0) {
-            b = a; a = new double[b.length];
-            for (int i = left - 1; ++i < right; a[i] = b[i]);
+            System.arraycopy(a, left, work, workBase, blen);
+            b = a; 
+            bo = 0;
+            a = work;
+            ao = workBase - left;
         } else {
-            b = new double[a.length];
+            b = work;
+            ao = 0;
+            bo = workBase - left;
         }
 
         // Merging
@@ -2660,17 +2714,17 @@
             for (int k = (last = 0) + 2; k <= count; k += 2) {
                 int hi = run[k], mi = run[k - 1];
                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
-                    if (q >= hi || p < mi && a[p] <= a[q]) {
-                        b[i] = a[p++];
+                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
+                        b[i + bo] = a[p++ + ao];
                     } else {
-                        b[i] = a[q++];
+                        b[i + bo] = a[q++ + ao];
                     }
                 }
                 run[++last] = hi;
             }
             if ((count & 1) != 0) {
                 for (int i = right, lo = run[count - 1]; --i >= lo;
-                    b[i] = a[i]
+                    b[i + bo] = a[i + ao]
                 );
                 run[++last] = right;
             }
--- a/src/share/classes/java/util/TimSort.java	Mon Apr 08 15:42:32 2013 +0200
+++ b/src/share/classes/java/util/TimSort.java	Mon Apr 08 16:05:54 2013 +0200
@@ -150,9 +150,10 @@
         int len = a.length;
         int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
             len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
-        if (work == null || workLen < tlen) {
+        if (work == null || workLen < tlen || workBase + tlen > work.length) {
             @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
-            T[] newArray = (T[]) new Object[tlen];
+            T[] newArray = (T[])java.lang.reflect.Array.newInstance
+                (a.getClass().getComponentType(), tlen);
             tmp = newArray;
             tmpBase = 0;
             tmpLen = tlen;
@@ -181,32 +182,30 @@
     }
 
     /*
-     * The next three methods (which are package private and static) constitute
-     * the entire API of this class.  Each of these methods obeys the contract
-     * of the public method with the same signature in java.util.Arrays.
+     * The next method (package private and static) constitutes the
+     * entire API of this class. 
      */
 
-    static <T> void sort(T[] a, Comparator<? super T> c) {
-        sort(a, 0, a.length, c, null, 0, 0);
-    }
-
-    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
-        sort(a, lo, hi, c, null, 0, 0);
-    }
-
     /**
-     * sort, using the given workspace array slice for temp storage
-     * when possible.
+     * Sorts the given range, using the given workspace array slice
+     * for temp storage when possible. This method is designed to be
+     * invoked from public methods (in class Arrays) after performing
+     * any necessary array bounds checks and expanding parameters into
+     * the required forms.
+     *
+     * @param a the array to be sorted
+     * @param lo the index of the first element, inclusive, to be sorted
+     * @param hi the index of the last element, exclusive, to be sorted
+     * @param c the comparator to use
+     * @param work a workspace array (slice)
+     * @param workBase origin of usable space in work array
+     * @param workLen usable size of work array
      * @since 1.8
      */
     static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                          T[] work, int workBase, int workLen) {
-        if (c == null) {
-            Arrays.sort(a, lo, hi);
-            return;
-        }
+        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
 
-        rangeCheck(a.length, lo, hi);
         int nRemaining  = hi - lo;
         if (nRemaining < 2)
             return;  // Arrays of size 0 and 1 are always sorted
@@ -926,32 +925,12 @@
                 newSize = Math.min(newSize, a.length >>> 1);
 
             @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
-            T[] newArray = (T[]) new Object[newSize];
+            T[] newArray = (T[])java.lang.reflect.Array.newInstance
+                (a.getClass().getComponentType(), newSize);
             tmp = newArray;
             tmpLen = newSize;
             tmpBase = 0;
         }
         return tmp;
     }
-
-    /**
-     * Checks that fromIndex and toIndex are in range, and throws an
-     * appropriate exception if they aren't.
-     *
-     * @param arrayLen the length of the array
-     * @param fromIndex the index of the first element of the range
-     * @param toIndex the index after the last element of the range
-     * @throws IllegalArgumentException if fromIndex > toIndex
-     * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
-     *         or toIndex > arrayLen
-     */
-    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
-        if (fromIndex > toIndex)
-            throw new IllegalArgumentException("fromIndex(" + fromIndex +
-                       ") > toIndex(" + toIndex+")");
-        if (fromIndex < 0)
-            throw new ArrayIndexOutOfBoundsException(fromIndex);
-        if (toIndex > arrayLen)
-            throw new ArrayIndexOutOfBoundsException(toIndex);
-    }
 }