changeset 14925:72729557c226

8003981: Support Parallel Array Sorting - JEP 103 Reviewed-by: chegar, forax, dholmes, dl Contributed-by: david.holmes@oracle.com, dl@cs.oswego.edu, chris.hegarty@oracle.com
author chegar
date Thu, 27 Dec 2012 21:55:24 +0000
parents 43383e2d85a6
children 1cb5d2255451
files jdk/make/java/java/FILES_java.gmk jdk/src/share/classes/java/util/Arrays.java jdk/src/share/classes/java/util/ArraysParallelSortHelpers.java jdk/test/java/util/Arrays/ParallelSorting.java
diffstat 4 files changed, 3916 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/jdk/make/java/java/FILES_java.gmk	Wed Dec 26 10:08:36 2012 -0500
+++ b/jdk/make/java/java/FILES_java.gmk	Thu Dec 27 21:55:24 2012 +0000
@@ -294,6 +294,7 @@
 	java/util/IdentityHashMap.java \
 	java/util/EnumMap.java \
     java/util/Arrays.java \
+    java/util/ArraysParallelSortHelpers.java \
     java/util/DualPivotQuicksort.java \
     java/util/TimSort.java \
     java/util/ComparableTimSort.java \
--- a/jdk/src/share/classes/java/util/Arrays.java	Wed Dec 26 10:08:36 2012 -0500
+++ b/jdk/src/share/classes/java/util/Arrays.java	Thu Dec 27 21:55:24 2012 +0000
@@ -26,6 +26,7 @@
 package java.util;
 
 import java.lang.reflect.*;
+import static java.util.ArraysParallelSortHelpers.*;
 
 /**
  * This class contains various methods for manipulating arrays (such as
@@ -54,6 +55,13 @@
  */
 public class Arrays {
 
+    /**
+     * The minimum array length below which the sorting algorithm will not
+     * further partition the sorting task.
+     */
+    // reasonable default so that we don't overcreate tasks
+    private static final int MIN_ARRAY_SORT_GRAN = 256;
+
     // Suppresses default constructor, ensuring non-instantiability.
     private Arrays() {}
 
@@ -787,6 +795,613 @@
         }
     }
 
+    /*
+     * Parallel sorting of primitive type arrays.
+     */
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(byte[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(byte[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(byte[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJByte.Sorter task = new FJByte.Sorter(a, new byte[a.length], fromIndex,
+                                               nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(char[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(char[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(char[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(char[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJChar.Sorter task = new FJChar.Sorter(a, new char[a.length], fromIndex,
+                                               nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(short[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(short[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(short[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(short[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJShort.Sorter task = new FJShort.Sorter(a, new short[a.length], fromIndex,
+                                                 nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(int[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(int[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(int[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(int[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJInt.Sorter task = new FJInt.Sorter(a, new int[a.length], fromIndex,
+                                             nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(long[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(long[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(long[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(long[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJLong.Sorter task = new FJLong.Sorter(a, new long[a.length], fromIndex,
+                                               nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>The {@code <} relation does not provide a total order on all float
+     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+     * other value and all {@code Float.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(float[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(float[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>The {@code <} relation does not provide a total order on all float
+     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+     * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+     * other value and all {@code Float.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(float[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(float[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJFloat.Sorter task = new FJFloat.Sorter(a, new float[a.length], fromIndex,
+                                                 nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>The {@code <} relation does not provide a total order on all double
+     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+     * other value and all {@code Double.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(double[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(double[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The range
+     * to be sorted extends from the index {@code fromIndex}, inclusive, to
+     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * the range to be sorted is empty.
+     *
+     * <p>The {@code <} relation does not provide a total order on all double
+     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+     * value compares neither less than, greater than, nor equal to any value,
+     * even itself. This method uses the total order imposed by the method
+     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+     * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+     * other value and all {@code Double.NaN} values are considered equal.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(double[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     *
+     * @since 1.8
+     */
+    public static void parallelSort(double[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        int gran = getSplitThreshold(nelements);
+        FJDouble.Sorter task = new FJDouble.Sorter(a, new double[a.length],
+                                                   fromIndex, nelements, gran);
+        task.invoke();
+    }
+
+    /*
+     * Parallel sorting of complex type arrays.
+     */
+
+    /**
+     * Sorts the specified array of objects into ascending order, according
+     * to the {@linkplain Comparable natural ordering} of its elements.
+     * All elements in the array must implement the {@link Comparable}
+     * interface.  Furthermore, all elements in the array must be
+     * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
+     * not throw a {@code ClassCastException} for any elements {@code e1}
+     * and {@code e2} in the array).
+     *
+     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
+     * may be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     *
+     * @throws ClassCastException if the array contains elements that are not
+     *         <i>mutually comparable</i> (for example, strings and integers)
+     * @throws IllegalArgumentException (optional) if the natural
+     *         ordering of the array elements is found to violate the
+     *         {@link Comparable} contract
+     *
+     * @since 1.8
+     */
+    public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
+        parallelSort(a, 0, a.length);
+    }
+
+    /**
+     * Sorts the specified range of the specified array of objects into
+     * ascending order, according to the
+     * {@linkplain Comparable natural ordering} of its
+     * elements.  The range to be sorted extends from index
+     * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
+     * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
+     * elements in this range must implement the {@link Comparable}
+     * interface.  Furthermore, all elements in this range must be <i>mutually
+     * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
+     * {@code ClassCastException} for any elements {@code e1} and
+     * {@code e2} in the array).
+     *
+     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
+     * may be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element (inclusive) to be
+     *        sorted
+     * @param toIndex the index of the last element (exclusive) to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+     *         (optional) if the natural ordering of the array elements is
+     *         found to violate the {@link Comparable} contract
+     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+     *         {@code toIndex > a.length}
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> (for example, strings and
+     *         integers).
+     *
+     * @since 1.8
+     */
+    public static <T extends Comparable<? super T>>
+            void parallelSort(T[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        Class<?> tc = a.getClass().getComponentType();
+        @SuppressWarnings("unchecked")
+        T[] workspace = (T[])Array.newInstance(tc, a.length);
+        int gran = getSplitThreshold(nelements);
+        FJComparable.Sorter<T> task = new FJComparable.Sorter<>(a, workspace,
+                                                                fromIndex,
+                                                                nelements, gran);
+        task.invoke();
+    }
+
+    /**
+     * Sorts the specified array of objects according to the order induced by
+     * the specified comparator.  All elements in the array must be
+     * <i>mutually comparable</i> by the specified comparator (that is,
+     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+     * for any elements {@code e1} and {@code e2} in the array).
+     *
+     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
+     * may be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param c the comparator to determine the order of the array.  A
+     *        {@code null} value indicates that the elements'
+     *        {@linkplain Comparable natural ordering} should be used.
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> using the specified comparator
+     * @throws IllegalArgumentException (optional) if the comparator is
+     *         found to violate the {@link java.util.Comparator} contract
+     *
+     * @since 1.8
+     */
+    public static <T> void parallelSort(T[] a, Comparator<? super T> c) {
+        parallelSort(a, 0, a.length, c);
+    }
+
+    /**
+     * Sorts the specified range of the specified array of objects according
+     * to the order induced by the specified comparator.  The range to be
+     * sorted extends from index {@code fromIndex}, inclusive, to index
+     * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
+     * range to be sorted is empty.)  All elements in the range must be
+     * <i>mutually comparable</i> by the specified comparator (that is,
+     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+     * for any elements {@code e1} and {@code e2} in the range).
+     *
+     * <p>This sort is not guaranteed to be <i>stable</i>:  equal elements
+     * may be reordered as a result of the sort.
+     *
+     * <p>Implementation note: The sorting algorithm is a parallel sort-merge
+     * that breaks the array into sub-arrays that are themselves sorted and then
+     * merged. When the sub-array length reaches a minimum granularity, the
+     * sub-array is sorted using the appropriate {@link Arrays#sort(Object[])
+     * Arrays.sort} method. The algorithm requires a working space equal to the
+     * size of the original array. The {@link
+     * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is
+     * used to execute any parallel tasks.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element (inclusive) to be
+     *        sorted
+     * @param toIndex the index of the last element (exclusive) to be sorted
+     * @param c the comparator to determine the order of the array.  A
+     *        {@code null} value indicates that the elements'
+     *        {@linkplain Comparable natural ordering} should be used.
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+     *         (optional) if the natural ordering of the array elements is
+     *         found to violate the {@link Comparable} contract
+     * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+     *         {@code toIndex > a.length}
+     * @throws ClassCastException if the array contains elements that are
+     *         not <i>mutually comparable</i> (for example, strings and
+     *         integers).
+     *
+     * @since 1.8
+     */
+    public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
+                                        Comparator<? super T> c) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        int nelements = toIndex - fromIndex;
+        Class<?> tc = a.getClass().getComponentType();
+        @SuppressWarnings("unchecked")
+        T[] workspace = (T[])Array.newInstance(tc, a.length);
+        int gran = getSplitThreshold(nelements);
+        FJComparator.Sorter<T> task = new FJComparator.Sorter<>(a, workspace,
+                                                                fromIndex,
+                                                                nelements, gran, c);
+        task.invoke();
+    }
+
+    /**
+     * Returns the size threshold for splitting into subtasks.
+     * By default, uses about 8 times as many tasks as threads
+     *
+     * @param n number of elements in the array to be processed
+     */
+    private static int getSplitThreshold(int n) {
+        int p = java.util.concurrent.ForkJoinPool.getCommonPoolParallelism();
+        int t = (p > 1) ? (1 + n / (p << 3)) : n;
+        return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;
+    }
+
     /**
      * Checks that {@code fromIndex} and {@code toIndex} are in
      * the range and throws an appropriate exception, if they aren't.
@@ -1480,9 +2095,9 @@
         while (low <= high) {
             int mid = (low + high) >>> 1;
             @SuppressWarnings("rawtypes")
-                Comparable midVal = (Comparable)a[mid];
+            Comparable midVal = (Comparable)a[mid];
             @SuppressWarnings("unchecked")
-                int cmp = midVal.compareTo(key);
+            int cmp = midVal.compareTo(key);
 
             if (cmp < 0)
                 low = mid + 1;
@@ -2847,19 +3462,20 @@
         private final E[] a;
 
         ArrayList(E[] array) {
-            if (array==null)
-                throw new NullPointerException();
-            a = array;
+            a = Objects.requireNonNull(array);
         }
 
+        @Override
         public int size() {
             return a.length;
         }
 
+        @Override
         public Object[] toArray() {
             return a.clone();
         }
 
+        @Override
         @SuppressWarnings("unchecked")
         public <T> T[] toArray(T[] a) {
             int size = size();
@@ -2872,16 +3488,19 @@
             return a;
         }
 
+        @Override
         public E get(int index) {
             return a[index];
         }
 
+        @Override
         public E set(int index, E element) {
             E oldValue = a[index];
             a[index] = element;
             return oldValue;
         }
 
+        @Override
         public int indexOf(Object o) {
             if (o==null) {
                 for (int i=0; i<a.length; i++)
@@ -2895,6 +3514,7 @@
             return -1;
         }
 
+        @Override
         public boolean contains(Object o) {
             return indexOf(o) != -1;
         }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/java/util/ArraysParallelSortHelpers.java	Thu Dec 27 21:55:24 2012 +0000
@@ -0,0 +1,1223 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.util;
+
+import java.util.concurrent.RecursiveAction;
+
+/**
+ * Helper utilities for the parallel sort methods in Arrays.parallelSort.
+ *
+ * For each primitive type, plus Object, we define a static class to
+ * contain the Sorter and Merger implementations for that type:
+ *
+ * Sorter classes based mainly on CilkSort
+ * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
+ * Basic algorithm:
+ * if array size is small, just use a sequential quicksort (via Arrays.sort)
+ *         Otherwise:
+ *         1. Break array in half.
+ *         2. For each half,
+ *             a. break the half in half (i.e., quarters),
+ *             b. sort the quarters
+ *             c. merge them together
+ *         3. merge together the two halves.
+ *
+ * One reason for splitting in quarters is that this guarantees
+ * that the final sort is in the main array, not the workspace
+ * array.  (workspace and main swap roles on each subsort step.)
+ * Leaf-level sorts use a Sequential quicksort, that in turn uses
+ * insertion sort if under threshold.  Otherwise it uses median of
+ * three to pick pivot, and loops rather than recurses along left
+ * path.
+ *
+ *
+ * Merger classes perform merging for Sorter. If big enough, splits 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. This is all messy to code; sadly we need
+ * distinct versions for each type.
+ *
+ */
+/*package*/ class ArraysParallelSortHelpers {
+
+    // RFE: we should only need a working array as large as the subarray
+    //      to be sorted, but the logic assumes that indices in the two
+    //      arrays always line-up
+
+    /** byte support class */
+    static final class FJByte {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 749471161188027634L;
+            final byte[] a;     // array to be sorted.
+            final byte[] w;     // workspace for merge
+            final int origin;   // origin of the part of array we deal with
+            final int n;        // Number of elements in (sub)arrays.
+            final int gran;     // split control
+
+            Sorter(byte[] a, byte[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final byte[] a = this.a;
+                final byte[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,  g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l+h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h,
+                               l+h, n-h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   //skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = -9090258248781844470L;
+            final byte[] a;
+            final byte[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(byte[] a, byte[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final byte[] a = this.a;
+                final byte[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    byte split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split <= a[ro + mid])
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    byte al = a[l];
+                    byte ar = a[r];
+                    byte t;
+                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJByte
+
+    /** char support class */
+    static final class FJChar {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 8723376019074596641L;
+            final char[] a;     // array to be sorted.
+            final char[] w;     // workspace for merge
+            final int origin;   // origin of the part of array we deal with
+            final int n;        // Number of elements in (sub)arrays.
+            final int gran;     // split control
+
+            Sorter(char[] a, char[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final char[] a = this.a;
+                final char[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = -1383975444621698926L;
+            final char[] a;
+            final char[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(char[] a, char[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final char[] a = this.a;
+                final char[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    char split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split <= a[ro + mid])
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    char al = a[l];
+                    char ar = a[r];
+                    char t;
+                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJChar
+
+    /** short support class */
+    static final class FJShort {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = -7886754793730583084L;
+            final short[] a;    // array to be sorted.
+            final short[] w;    // workspace for merge
+            final int origin;   // origin of the part of array we deal with
+            final int n;        // Number of elements in (sub)arrays.
+            final int gran;     // split control
+
+            Sorter(short[] a, short[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final short[] a = this.a;
+                final short[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = 3895749408536700048L;
+            final short[] a;
+            final short[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(short[] a, short[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final short[] a = this.a;
+                final short[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    short split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split <= a[ro + mid])
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    short al = a[l];
+                    short ar = a[r];
+                    short t;
+                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJShort
+
+    /** int support class */
+    static final class FJInt {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 4263311808957292729L;
+            final int[] a;     // array to be sorted.
+            final int[] w;     // workspace for merge
+            final int origin;  // origin of the part of array we deal with
+            final int n;       // Number of elements in (sub)arrays.
+            final int gran;    // split control
+
+            Sorter(int[] a, int[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final int[] a = this.a;
+                final int[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = -8727507284219982792L;
+            final int[] a;
+            final int[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(int[] a, int[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final int[] a = this.a;
+                final int[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    int split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split <= a[ro + mid])
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    int al = a[l];
+                    int ar = a[r];
+                    int t;
+                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJInt
+
+    /** long support class */
+    static final class FJLong {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 6553695007444392455L;
+            final long[] a;     // array to be sorted.
+            final long[] w;     // workspace for merge
+            final int origin;   // origin of the part of array we deal with
+            final int n;        // Number of elements in (sub)arrays.
+            final int gran;     // split control
+
+            Sorter(long[] a, long[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final long[] a = this.a;
+                final long[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = 8843567516333283861L;
+            final long[] a;
+            final long[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final long[] a = this.a;
+                final long[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    long split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split <= a[ro + mid])
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                      nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    long al = a[l];
+                    long ar = a[r];
+                    long t;
+                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJLong
+
+    /** float support class */
+    static final class FJFloat {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 1602600178202763377L;
+            final float[] a;    // array to be sorted.
+            final float[] w;    // workspace for merge
+            final int origin;   // origin of the part of array we deal with
+            final int n;        // Number of elements in (sub)arrays.
+            final int gran;     // split control
+
+            Sorter(float[] a, float[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final float[] a = this.a;
+                final float[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = 1518176433845397426L;
+            final float[] a;
+            final float[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(float[] a, float[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final float[] a = this.a;
+                final float[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    float split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (Float.compare(split, a[ro+mid]) <= 0)
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    float al = a[l];
+                    float ar = a[r];
+                    float t;
+                    if (Float.compare(al, ar) <= 0) {
+                        ++l;
+                        t = al;
+                    } else {
+                        ++r;
+                        t = ar;
+                    }
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJFloat
+
+    /** double support class */
+    static final class FJDouble {
+        static final class Sorter extends RecursiveAction {
+            static final long serialVersionUID = 2446542900576103244L;
+            final double[] a;    // array to be sorted.
+            final double[] w;    // workspace for merge
+            final int origin;    // origin of the part of array we deal with
+            final int n;         // Number of elements in (sub)arrays.
+            final int gran;      // split control
+
+            Sorter(double[] a, double[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final double[] a = this.a;
+                final double[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),
+                                                     new Sorter(a, w, l+q, h-q, g),
+                                                     new Merger(a, w, l,   q,
+                                                                l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),
+                                                     new Sorter(a, w, l+u, n-u, g),
+                                                     new Merger(a, w, l+h, q,
+                                                                l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck
+                }
+            }
+        }
+
+        static final class Merger extends RecursiveAction {
+            static final long serialVersionUID = 8076242187166127592L;
+            final double[] a;
+            final double[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger next;
+
+            Merger(double[] a, double[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final double[] a = this.a;
+                final double[] w = this.w;
+                Merger rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    double split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (Double.compare(split, a[ro+mid]) <= 0)
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
+                                         nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    double al = a[l];
+                    double ar = a[r];
+                    double t;
+                    if (Double.compare(al, ar) <= 0) {
+                        ++l;
+                        t = al;
+                    } else {
+                        ++r;
+                        t = ar;
+                    }
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJDouble
+
+    /** Comparable support class */
+    static final class FJComparable {
+        static final class Sorter<T extends Comparable<? super T>> extends RecursiveAction {
+            static final long serialVersionUID = -1024003289463302522L;
+            final T[] a;
+            final T[] w;
+            final int origin;
+            final int n;
+            final int gran;
+
+            Sorter(T[] a, T[] w, int origin, int n, int gran) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final T[] a = this.a;
+                final T[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1;
+                    int q = n >>> 2;
+                    int u = h + q;
+                    FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q,   g),
+                                                     new Sorter<>(a, w, l+q, h-q, g),
+                                                     new Merger<>(a, w, l,   q,
+                                                                  l+q, h-q, l, g, null));
+                    FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l+h, q,   g),
+                                                     new Sorter<>(a, w, l+u, n-u, g),
+                                                     new Merger<>(a, w, l+h, q,
+                                                                  l+u, n-u, l+h, g, null));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger<>(w, a, l, h, l + h, n - h, l, g, null).compute();
+                } else {
+                    Arrays.sort(a, l, l+n);
+                }
+            }
+        }
+
+        static final class Merger<T extends Comparable<? super T>> extends RecursiveAction {
+            static final long serialVersionUID = -3989771675258379302L;
+            final T[] a;
+            final T[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger<T> next;
+
+            Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger<T> next) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+            }
+
+            public void compute() {
+                final T[] a = this.a;
+                final T[] w = this.w;
+                Merger<T> rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    T split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (split.compareTo(a[ro + mid]) <= 0)
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh,
+                                           nright-rh, wo+lh+rh, gran, rights)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    T al = a[l];
+                    T ar = a[r];
+                    T t;
+                    if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; }
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJComparable
+
+    /** Object + Comparator support class */
+    static final class FJComparator {
+        static final class Sorter<T> extends RecursiveAction {
+            static final long serialVersionUID = 9191600840025808581L;
+            final T[] a;       // array to be sorted.
+            final T[] w;       // workspace for merge
+            final int origin;  // origin of the part of array we deal with
+            final int n;       // Number of elements in (sub)arrays.
+            final int gran;    // split control
+            final Comparator<? super T> cmp; // Comparator to use
+
+            Sorter(T[] a, T[] w, int origin, int n, int gran, Comparator<? super T> cmp) {
+                this.a = a;
+                this.w = w;
+                this.origin = origin;
+                this.n = n;
+                this.cmp = cmp;
+                this.gran = gran;
+            }
+
+            public void compute() {
+                final int l = origin;
+                final int g = gran;
+                final int n = this.n;
+                final T[] a = this.a;
+                final T[] w = this.w;
+                if (n > g) {
+                    int h = n >>> 1; // half
+                    int q = n >>> 2; // lower quarter index
+                    int u = h + q;   // upper quarter
+                    FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q,   g, cmp),
+                                                     new Sorter<>(a, w, l+q, h-q, g, cmp),
+                                                     new Merger<>(a, w, l,   q,
+                                                                  l+q, h-q, l, g, null, cmp));
+                    FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l + h, q,   g, cmp),
+                                                     new Sorter<>(a, w, l+u, n-u, g, cmp),
+                                                     new Merger<>(a, w, l+h, q,
+                                                                  l+u, n-u, l+h, g, null, cmp));
+                    rs.fork();
+                    ls.compute();
+                    if (rs.tryUnfork()) rs.compute(); else rs.join();
+                    new Merger<>(w, a, l, h, l + h, n - h, l, g, null, cmp).compute();
+                } else {
+                    Arrays.sort(a, l, l+n, cmp);
+                }
+            }
+        }
+
+        static final class Merger<T> extends RecursiveAction {
+            static final long serialVersionUID = -2679539040379156203L;
+            final T[] a;
+            final T[] w;
+            final int lo;
+            final int ln;
+            final int ro;
+            final int rn;
+            final int wo;
+            final int gran;
+            final Merger<T> next;
+            final Comparator<? super T> cmp;
+
+            Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo,
+                   int gran, Merger<T> next, Comparator<? super T> cmp) {
+                this.a = a;
+                this.w = w;
+                this.lo = lo;
+                this.ln = ln;
+                this.ro = ro;
+                this.rn = rn;
+                this.wo = wo;
+                this.gran = gran;
+                this.next = next;
+                this.cmp = cmp;
+            }
+
+            public void compute() {
+                final T[] a = this.a;
+                final T[] w = this.w;
+                Merger<T> rights = null;
+                int nleft = ln;
+                int nright = rn;
+                while (nleft > gran) {
+                    int lh = nleft >>> 1;
+                    int splitIndex = lo + lh;
+                    T split = a[splitIndex];
+                    int rl = 0;
+                    int rh = nright;
+                    while (rl < rh) {
+                        int mid = (rl + rh) >>> 1;
+                        if (cmp.compare(split, a[ro+mid]) <= 0)
+                            rh = mid;
+                        else
+                            rl = mid + 1;
+                    }
+                    (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh,
+                                           nright-rh, wo+lh+rh, gran, rights, cmp)).fork();
+                    nleft = lh;
+                    nright = rh;
+                }
+
+                int l = lo;
+                int lFence = l + nleft;
+                int r = ro;
+                int rFence = r + nright;
+                int k = wo;
+                while (l < lFence && r < rFence) {
+                    T al = a[l];
+                    T ar = a[r];
+                    T t;
+                    if (cmp.compare(al, ar) <= 0) {
+                        ++l;
+                        t = al;
+                    } else {
+                        ++r;
+                        t = ar;
+                    }
+                    w[k++] = t;
+                }
+                while (l < lFence)
+                    w[k++] = a[l++];
+                while (r < rFence)
+                    w[k++] = a[r++];
+                while (rights != null) {
+                    if (rights.tryUnfork())
+                        rights.compute();
+                    else
+                        rights.join();
+                    rights = rights.next;
+                }
+            }
+        }
+    } // FJComparator
+
+    /** Utility class to sort half a partitioned array */
+    private static final class FJSubSorter extends RecursiveAction {
+        static final long serialVersionUID = 9159249695527935512L;
+        final RecursiveAction left;
+        final RecursiveAction right;
+        final RecursiveAction merger;
+
+        FJSubSorter(RecursiveAction left, RecursiveAction right,
+                    RecursiveAction merger) {
+            this.left = left;
+            this.right = right;
+            this.merger = merger;
+        }
+
+        public void compute() {
+            right.fork();
+            left.invoke();
+            right.join();
+            merger.invoke();
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Arrays/ParallelSorting.java	Thu Dec 27 21:55:24 2012 +0000
@@ -0,0 +1,2067 @@
+/*
+ * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/* Adapted from test/java/util/Arrays/Sorting.java
+ *
+ * Where that test checks Arrays.sort against manual quicksort routines,
+ * this test checks parallelSort against either Arrays.sort or manual
+ * quicksort routines.
+ */
+
+/*
+ * @test
+ * @bug 8003981
+ * @run main ParallelSorting -shortrun
+ * @summary Exercise Arrays.parallelSort (adapted from test Sorting)
+ *
+ * @author Vladimir Yaroslavskiy
+ * @author Jon Bentley
+ * @author Josh Bloch
+ */
+
+import java.util.Arrays;
+import java.util.Random;
+import java.io.PrintStream;
+import java.util.Comparator;
+
+public class ParallelSorting {
+    private static final PrintStream out = System.out;
+    private static final PrintStream err = System.err;
+
+    // Array lengths used in a long run (default)
+    private static final int[] LONG_RUN_LENGTHS = {
+        1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
+
+    // Array lengths used in a short run
+    private static final int[] SHORT_RUN_LENGTHS = {
+        1, 2, 3, 21, 55, 1000, 10000 };
+
+    // Random initial values used in a long run (default)
+    private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
+
+    // Random initial values used in a short run
+    private static final long[] SHORT_RUN_RANDOMS = { 666 };
+
+    public static void main(String[] args) {
+        boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
+        long start = System.currentTimeMillis();
+
+        if (shortRun) {
+            testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
+        } else {
+            testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
+        }
+        long end = System.currentTimeMillis();
+
+        out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
+    }
+
+    private static void testAndCheck(int[] lengths, long[] randoms) {
+        testEmptyAndNullIntArray();
+        testEmptyAndNullLongArray();
+        testEmptyAndNullShortArray();
+        testEmptyAndNullCharArray();
+        testEmptyAndNullByteArray();
+        testEmptyAndNullFloatArray();
+        testEmptyAndNullDoubleArray();
+
+        for (int length : lengths) {
+            testMergeSort(length);
+            testAndCheckRange(length);
+            testAndCheckSubArray(length);
+        }
+        for (long seed : randoms) {
+            for (int length : lengths) {
+                testAndCheckWithInsertionSort(length, new MyRandom(seed));
+                testAndCheckWithCheckSum(length, new MyRandom(seed));
+                testAndCheckWithScrambling(length, new MyRandom(seed));
+                testAndCheckFloat(length, new MyRandom(seed));
+                testAndCheckDouble(length, new MyRandom(seed));
+                testStable(length, new MyRandom(seed));
+            }
+        }
+    }
+
+    private static void testEmptyAndNullIntArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new int[]{});
+        Arrays.parallelSort(new int[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((int[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((int[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(int[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(int[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullLongArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new long[]{});
+        Arrays.parallelSort(new long[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((long[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((long[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(long[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(long[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullShortArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new short[]{});
+        Arrays.parallelSort(new short[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((short[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((short[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(short[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(short[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullCharArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new char[]{});
+        Arrays.parallelSort(new char[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((char[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((char[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(char[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(char[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullByteArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new byte[]{});
+        Arrays.parallelSort(new byte[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((byte[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((byte[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(byte[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(byte[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullFloatArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new float[]{});
+        Arrays.parallelSort(new float[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((float[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((float[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(float[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(float[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullDoubleArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.parallelSort(new double[]{});
+        Arrays.parallelSort(new double[]{}, 0, 0);
+
+        try {
+            Arrays.parallelSort((double[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.parallelSort((double[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.parallelSort(double[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.parallelSort(double[]) shouldn't catch null array");
+    }
+
+    private static void testAndCheckSubArray(int length) {
+        ourDescription = "Check sorting of subarray";
+        int[] golden = new int[length];
+        boolean newLine = false;
+
+        for (int m = 1; m < length / 2; m *= 2) {
+            newLine = true;
+            int fromIndex = m;
+            int toIndex = length - m;
+
+            prepareSubArray(golden, fromIndex, toIndex, m);
+            int[] test = golden.clone();
+
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test 'subarray': " + converter +
+                   " length = " + length + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                Object convertedTest = converter.convert(test);
+                sortSubArray(convertedTest, fromIndex, toIndex);
+                checkSubArray(convertedTest, fromIndex, toIndex, m);
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void testAndCheckRange(int length) {
+        ourDescription = "Check range check";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (int i = 1; i <= length; i++) {
+                golden[i - 1] = i % m + m % i;
+            }
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test 'range': " + converter +
+                   ", length = " + length + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                checkRange(convertedGolden, m);
+            }
+        }
+        out.println();
+    }
+
+    private static void testStable(int length, MyRandom random) {
+        ourDescription = "Check if sorting is stable";
+        Pair[] a = build(length, random);
+
+        out.println("Test 'stable': " + "random = " + random.getSeed() +
+            ", length = " + length);
+        Arrays.parallelSort(a);
+        checkSorted(a);
+        checkStable(a);
+        out.println();
+
+        a = build(length, random);
+
+        out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +
+            ", length = " + length);
+        Arrays.parallelSort(a, pairCmp);
+        checkSorted(a);
+        checkStable(a);
+        out.println();
+
+    }
+
+    private static void checkSorted(Pair[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].getKey() > a[i + 1].getKey()) {
+                failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
+            }
+        }
+    }
+
+    private static void checkStable(Pair[] a) {
+        for (int i = 0; i < a.length / 4; ) {
+            int key1 = a[i].getKey();
+            int value1 = a[i++].getValue();
+            int key2 = a[i].getKey();
+            int value2 = a[i++].getValue();
+            int key3 = a[i].getKey();
+            int value3 = a[i++].getValue();
+            int key4 = a[i].getKey();
+            int value4 = a[i++].getValue();
+
+            if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
+                failed("On position " + i + " keys are different " +
+                    key1 + ", " + key2 + ", " + key3 + ", " + key4);
+            }
+            if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
+                failed("Sorting is not stable at position " + i +
+                    ". Second values have been changed: " +  value1 + ", " +
+                    value2 + ", " + value3 + ", " + value4);
+            }
+        }
+    }
+
+    private static Pair[] build(int length, Random random) {
+        Pair[] a = new Pair[length * 4];
+
+        for (int i = 0; i < a.length; ) {
+            int key = random.nextInt();
+            a[i++] = new Pair(key, 1);
+            a[i++] = new Pair(key, 2);
+            a[i++] = new Pair(key, 3);
+            a[i++] = new Pair(key, 4);
+        }
+        return a;
+    }
+
+    private static Comparator<Pair> pairCmp = new Comparator<Pair>() {
+        public int compare(Pair p1, Pair p2) {
+            return p1.compareTo(p2);
+        }
+    };
+
+    private static final class Pair implements Comparable<Pair> {
+        Pair(int key, int value) {
+            myKey = key;
+            myValue = value;
+        }
+
+        int getKey() {
+            return myKey;
+        }
+
+        int getValue() {
+            return myValue;
+        }
+
+        public int compareTo(Pair pair) {
+            if (myKey < pair.myKey) {
+                return -1;
+            }
+            if (myKey > pair.myKey) {
+                return 1;
+            }
+            return 0;
+        }
+
+        @Override
+        public String toString() {
+            return "(" + myKey + ", " + myValue + ")";
+        }
+
+        private int myKey;
+        private int myValue;
+    }
+
+
+    private static void testAndCheckWithInsertionSort(int length, MyRandom random) {
+        if (length > 1000) {
+            return;
+        }
+        ourDescription = "Check sorting with insertion sort";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+                builder.build(golden, m, random);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'insertion sort': " + converter +
+                        " " + builder + "random = " + random.getSeed() +
+                        ", length = " + length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest1 = converter.convert(test);
+                    Object convertedTest2 = converter.convert(test);
+                    sort(convertedTest1);
+                    sortByInsertionSort(convertedTest2);
+                    compare(convertedTest1, convertedTest2);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testMergeSort(int length) {
+        if (length < 1000) {
+            return;
+        }
+        ourDescription = "Check merge sorting";
+        int[] golden = new int[length];
+        int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
+
+        for (int m = period - 2; m <= period + 2; m++) {
+            for (MergeBuilder builder : MergeBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'merge sort': " + converter + " " +
+                        builder + "length = " + length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    sort(convertedGolden);
+                    checkSorted(convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithCheckSum(int length, MyRandom random) {
+        ourDescription = "Check sorting with check sum";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+                builder.build(golden, m, random);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'check sum': " + converter +
+                        " " + builder + "random = " + random.getSeed() +
+                        ", length = " + length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    checkWithCheckSum(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithScrambling(int length, MyRandom random) {
+        ourDescription = "Check sorting with scrambling";
+        int[] golden = new int[length];
+
+        for (int m = 1; m <= 7; m++) {
+            if (m > length) {
+                break;
+            }
+            for (SortedBuilder builder : SortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+                scramble(test, random);
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'scrambling': " + converter +
+                       " " + builder + "random = " + random.getSeed() +
+                       ", length = " + length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    compare(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckFloat(int length, MyRandom random) {
+        ourDescription = "Check float sorting";
+        float[] golden = new float[length];
+        final int MAX = 10;
+        boolean newLine = false;
+
+        for (int a = 0; a <= MAX; a++) {
+            for (int g = 0; g <= MAX; g++) {
+                for (int z = 0; z <= MAX; z++) {
+                    for (int n = 0; n <= MAX; n++) {
+                        for (int p = 0; p <= MAX; p++) {
+                            if (a + g + z + n + p > length) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < length) {
+                                continue;
+                            }
+                            for (FloatBuilder builder : FloatBuilder.values()) {
+                                out.println("Test 'float': random = " + random.getSeed() +
+                                   ", length = " + length + ", a = " + a + ", g = " +
+                                   g + ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p, random);
+                                float[] test = golden.clone();
+                                scramble(test, random);
+                                sort(test);
+                                compare(test, golden, a, n, g);
+                            }
+                            newLine = true;
+                        }
+                    }
+                }
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void testAndCheckDouble(int length, MyRandom random) {
+        ourDescription = "Check double sorting";
+        double[] golden = new double[length];
+        final int MAX = 10;
+        boolean newLine = false;
+
+        for (int a = 0; a <= MAX; a++) {
+            for (int g = 0; g <= MAX; g++) {
+                for (int z = 0; z <= MAX; z++) {
+                    for (int n = 0; n <= MAX; n++) {
+                        for (int p = 0; p <= MAX; p++) {
+                            if (a + g + z + n + p > length) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < length) {
+                                continue;
+                            }
+                            for (DoubleBuilder builder : DoubleBuilder.values()) {
+                                out.println("Test 'double': random = " + random.getSeed() +
+                                   ", length = " + length + ", a = " + a + ", g = " +
+                                   g + ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p, random);
+                                double[] test = golden.clone();
+                                scramble(test, random);
+                                sort(test);
+                                compare(test, golden, a, n, g);
+                            }
+                            newLine = true;
+                        }
+                    }
+                }
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
+
+    private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            a[i] = 0xDEDA;
+        }
+        int middle = (fromIndex + toIndex) >>> 1;
+        int k = 0;
+
+        for (int i = fromIndex; i < middle; i++) {
+            a[i] = k++;
+        }
+        for (int i = middle; i < toIndex; i++) {
+            a[i] = k--;
+        }
+        for (int i = toIndex; i < a.length; i++) {
+            a[i] = 0xBABA;
+        }
+    }
+
+    private static void scramble(int[] a, Random random) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
+        }
+    }
+
+    private static void scramble(float[] a, Random random) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
+        }
+    }
+
+    private static void scramble(double[] a, Random random) {
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
+        }
+    }
+
+    private static void swap(int[] a, int i, int j) {
+        int t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static void swap(float[] a, int i, int j) {
+        float t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static void swap(double[] a, int i, int j) {
+        double t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static enum TypeConverter {
+        INT {
+            Object convert(int[] a) {
+                return a.clone();
+            }
+        },
+        LONG {
+            Object convert(int[] a) {
+                long[] b = new long[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (long) a[i];
+                }
+                return b;
+            }
+        },
+        BYTE {
+            Object convert(int[] a) {
+                byte[] b = new byte[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (byte) a[i];
+                }
+                return b;
+            }
+        },
+        SHORT {
+            Object convert(int[] a) {
+                short[] b = new short[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (short) a[i];
+                }
+                return b;
+            }
+        },
+        CHAR {
+            Object convert(int[] a) {
+                char[] b = new char[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (char) a[i];
+                }
+                return b;
+            }
+        },
+        FLOAT {
+            Object convert(int[] a) {
+                float[] b = new float[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (float) a[i];
+                }
+                return b;
+            }
+        },
+        DOUBLE {
+            Object convert(int[] a) {
+                double[] b = new double[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = (double) a[i];
+                }
+                return b;
+            }
+        },
+        INTEGER {
+            Object convert(int[] a) {
+                Integer[] b = new Integer[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = new Integer(a[i]);
+                }
+                return b;
+            }
+        };
+
+        abstract Object convert(int[] a);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 9; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static enum FloatBuilder {
+        SIMPLE {
+            void build(float[] x, int a, int g, int z, int n, int p, Random random) {
+                int fromIndex = 0;
+                float negativeValue = -random.nextFloat();
+                float positiveValue =  random.nextFloat();
+
+                writeValue(x, negativeValue, fromIndex, n);
+                fromIndex += n;
+
+                writeValue(x, -0.0f, fromIndex, g);
+                fromIndex += g;
+
+                writeValue(x, 0.0f, fromIndex, z);
+                fromIndex += z;
+
+                writeValue(x, positiveValue, fromIndex, p);
+                fromIndex += p;
+
+                writeValue(x, Float.NaN, fromIndex, a);
+            }
+        };
+
+        abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
+    }
+
+    private static enum DoubleBuilder {
+        SIMPLE {
+            void build(double[] x, int a, int g, int z, int n, int p, Random random) {
+                int fromIndex = 0;
+                double negativeValue = -random.nextFloat();
+                double positiveValue =  random.nextFloat();
+
+                writeValue(x, negativeValue, fromIndex, n);
+                fromIndex += n;
+
+                writeValue(x, -0.0d, fromIndex, g);
+                fromIndex += g;
+
+                writeValue(x, 0.0d, fromIndex, z);
+                fromIndex += z;
+
+                writeValue(x, positiveValue, fromIndex, p);
+                fromIndex += p;
+
+                writeValue(x, Double.NaN, fromIndex, a);
+            }
+        };
+
+        abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);
+    }
+
+    private static void writeValue(float[] a, float value, int fromIndex, int count) {
+        for (int i = fromIndex; i < fromIndex + count; i++) {
+            a[i] = value;
+        }
+    }
+
+    private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
+        for (int i = a.length - numNaN; i < a.length; i++) {
+            if (a[i] == a[i]) {
+                failed("On position " + i + " must be NaN instead of " + a[i]);
+            }
+        }
+        final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+
+        for (int i = numNeg; i < numNeg + numNegZero; i++) {
+            if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
+                failed("On position " + i + " must be -0.0 instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void writeValue(double[] a, double value, int fromIndex, int count) {
+        for (int i = fromIndex; i < fromIndex + count; i++) {
+            a[i] = value;
+        }
+    }
+
+    private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
+        for (int i = a.length - numNaN; i < a.length; i++) {
+            if (a[i] == a[i]) {
+                failed("On position " + i + " must be NaN instead of " + a[i]);
+            }
+        }
+        final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+
+        for (int i = numNeg; i < numNeg + numNegZero; i++) {
+            if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
+                failed("On position " + i + " must be -0.0 instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static enum SortedBuilder {
+        REPEATED {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int i = 0;
+                int k = 0;
+
+                while (true) {
+                    for (int t = 1; t <= period; t++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = k;
+                    }
+                    if (i >= a.length) {
+                        return;
+                    }
+                    k++;
+                }
+            }
+        },
+        ORGAN_PIPES {
+            void build(int[] a, int m) {
+                int i = 0;
+                int k = m;
+
+                while (true) {
+                    for (int t = 1; t <= m; t++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = k;
+                    }
+                }
+            }
+        };
+
+        abstract void build(int[] a, int m);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static enum MergeBuilder {
+        ASCENDING {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int v = 1, i = 0;
+
+                for (int k = 0; k < m; k++) {
+                    v = 1;
+                    for (int p = 0; p < period; p++) {
+                        a[i++] = v++;
+                    }
+                }
+                for (int j = i; j < a.length - 1; j++) {
+                    a[j] = v++;
+                }
+                a[a.length - 1] = 0;
+            }
+        },
+        DESCENDING {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int v = -1, i = 0;
+
+                for (int k = 0; k < m; k++) {
+                    v = -1;
+                    for (int p = 0; p < period; p++) {
+                        a[i++] = v--;
+                    }
+                }
+                for (int j = i; j < a.length - 1; j++) {
+                    a[j] = v--;
+                }
+                a[a.length - 1] = 0;
+            }
+        };
+
+        abstract void build(int[] a, int m);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static enum UnsortedBuilder {
+        RANDOM {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = random.nextInt();
+                }
+            }
+        },
+        ASCENDING {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = m + i;
+                }
+            }
+        },
+        DESCENDING {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = a.length - m - i;
+                }
+            }
+        },
+        ALL_EQUAL {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = m;
+                }
+            }
+        },
+        SAW {
+            void build(int[] a, int m, Random random) {
+                int incCount = 1;
+                int decCount = a.length;
+                int i = 0;
+                int period = m--;
+
+                while (true) {
+                    for (int k = 1; k <= period; k++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = incCount++;
+                    }
+                    period += m;
+
+                    for (int k = 1; k <= period; k++) {
+                        if (i >= a.length) {
+                            return;
+                        }
+                        a[i++] = decCount--;
+                    }
+                    period += m;
+                }
+            }
+        },
+        REPEATED {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = i % m;
+                }
+            }
+        },
+        DUPLICATED {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = random.nextInt(m);
+                }
+            }
+        },
+        ORGAN_PIPES {
+            void build(int[] a, int m, Random random) {
+                int middle = a.length / (m + 1);
+
+                for (int i = 0; i < middle; i++) {
+                    a[i] = i;
+                }
+                for (int i = middle; i < a.length; i++) {
+                    a[i] = a.length - i - 1;
+                }
+            }
+        },
+        STAGGER {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = (i * m + i) % a.length;
+                }
+            }
+        },
+        PLATEAU {
+            void build(int[] a, int m, Random random) {
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = Math.min(i, m);
+                }
+            }
+        },
+        SHUFFLE {
+            void build(int[] a, int m, Random random) {
+                int x = 0, y = 0;
+                for (int i = 0; i < a.length; i++) {
+                    a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
+                }
+            }
+        };
+
+        abstract void build(int[] a, int m, Random random);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
+    private static void checkWithCheckSum(Object test, Object golden) {
+        checkSorted(test);
+        checkCheckSum(test, golden);
+    }
+
+    private static void failed(String message) {
+        err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
+        throw new RuntimeException("Test failed - see log file for details");
+    }
+
+    private static void failedSort(int index, String value1, String value2) {
+        failed("Array is not sorted at " + index + "-th position: " +
+            value1 + " and " + value2);
+    }
+
+    private static void failedCompare(int index, String value1, String value2) {
+        failed("On position " + index + " must be " + value2 + " instead of " + value1);
+    }
+
+    private static void compare(Object test, Object golden) {
+        if (test instanceof int[]) {
+            compare((int[]) test, (int[]) golden);
+        } else if (test instanceof long[]) {
+            compare((long[]) test, (long[]) golden);
+        } else if (test instanceof short[]) {
+            compare((short[]) test, (short[]) golden);
+        } else if (test instanceof byte[]) {
+            compare((byte[]) test, (byte[]) golden);
+        } else if (test instanceof char[]) {
+            compare((char[]) test, (char[]) golden);
+        } else if (test instanceof float[]) {
+            compare((float[]) test, (float[]) golden);
+        } else if (test instanceof double[]) {
+            compare((double[]) test, (double[]) golden);
+        } else if (test instanceof Integer[]) {
+            compare((Integer[]) test, (Integer[]) golden);
+        } else {
+            failed("Unknow type of array: " + test + " of class " +
+                test.getClass().getName());
+        }
+    }
+
+    private static void compare(int[] a, int[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(long[] a, long[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(short[] a, short[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(byte[] a, byte[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(char[] a, char[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(float[] a, float[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(double[] a, double[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void compare(Integer[] a, Integer[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i].compareTo(b[i]) != 0) {
+                failedCompare(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void checkSorted(Object object) {
+        if (object instanceof int[]) {
+            checkSorted((int[]) object);
+        } else if (object instanceof long[]) {
+            checkSorted((long[]) object);
+        } else if (object instanceof short[]) {
+            checkSorted((short[]) object);
+        } else if (object instanceof byte[]) {
+            checkSorted((byte[]) object);
+        } else if (object instanceof char[]) {
+            checkSorted((char[]) object);
+        } else if (object instanceof float[]) {
+            checkSorted((float[]) object);
+        } else if (object instanceof double[]) {
+            checkSorted((double[]) object);
+        } else if (object instanceof Integer[]) {
+            checkSorted((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSorted(int[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(long[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(short[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(byte[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(char[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(float[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(double[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkSorted(Integer[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
+    private static void checkCheckSum(Object test, Object golden) {
+        if (checkSumXor(test) != checkSumXor(golden)) {
+            failed("Original and sorted arrays are not identical [xor]");
+        }
+        if (checkSumPlus(test) != checkSumPlus(golden)) {
+            failed("Original and sorted arrays are not identical [plus]");
+        }
+    }
+
+    private static int checkSumXor(Object object) {
+        if (object instanceof int[]) {
+            return checkSumXor((int[]) object);
+        } else if (object instanceof long[]) {
+            return checkSumXor((long[]) object);
+        } else if (object instanceof short[]) {
+            return checkSumXor((short[]) object);
+        } else if (object instanceof byte[]) {
+            return checkSumXor((byte[]) object);
+        } else if (object instanceof char[]) {
+            return checkSumXor((char[]) object);
+        } else if (object instanceof float[]) {
+            return checkSumXor((float[]) object);
+        } else if (object instanceof double[]) {
+            return checkSumXor((double[]) object);
+        } else if (object instanceof Integer[]) {
+            return checkSumXor((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+            return -1;
+        }
+    }
+
+    private static int checkSumXor(Integer[] a) {
+        int checkSum = 0;
+
+        for (Integer e : a) {
+            checkSum ^= e.intValue();
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(int[] a) {
+        int checkSum = 0;
+
+        for (int e : a) {
+            checkSum ^= e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(long[] a) {
+        long checkSum = 0;
+
+        for (long e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(short[] a) {
+        short checkSum = 0;
+
+        for (short e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(byte[] a) {
+        byte checkSum = 0;
+
+        for (byte e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(char[] a) {
+        char checkSum = 0;
+
+        for (char e : a) {
+            checkSum ^= e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumXor(float[] a) {
+        int checkSum = 0;
+
+        for (float e : a) {
+            checkSum ^= (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumXor(double[] a) {
+        int checkSum = 0;
+
+        for (double e : a) {
+            checkSum ^= (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(Object object) {
+        if (object instanceof int[]) {
+            return checkSumPlus((int[]) object);
+        } else if (object instanceof long[]) {
+            return checkSumPlus((long[]) object);
+        } else if (object instanceof short[]) {
+            return checkSumPlus((short[]) object);
+        } else if (object instanceof byte[]) {
+            return checkSumPlus((byte[]) object);
+        } else if (object instanceof char[]) {
+            return checkSumPlus((char[]) object);
+        } else if (object instanceof float[]) {
+            return checkSumPlus((float[]) object);
+        } else if (object instanceof double[]) {
+            return checkSumPlus((double[]) object);
+        } else if (object instanceof Integer[]) {
+            return checkSumPlus((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+            return -1;
+        }
+    }
+
+    private static int checkSumPlus(int[] a) {
+        int checkSum = 0;
+
+        for (int e : a) {
+            checkSum += e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(long[] a) {
+        long checkSum = 0;
+
+        for (long e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(short[] a) {
+        short checkSum = 0;
+
+        for (short e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(byte[] a) {
+        byte checkSum = 0;
+
+        for (byte e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(char[] a) {
+        char checkSum = 0;
+
+        for (char e : a) {
+            checkSum += e;
+        }
+        return (int) checkSum;
+    }
+
+    private static int checkSumPlus(float[] a) {
+        int checkSum = 0;
+
+        for (float e : a) {
+            checkSum += (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(double[] a) {
+        int checkSum = 0;
+
+        for (double e : a) {
+            checkSum += (int) e;
+        }
+        return checkSum;
+    }
+
+    private static int checkSumPlus(Integer[] a) {
+        int checkSum = 0;
+
+        for (Integer e : a) {
+            checkSum += e.intValue();
+        }
+        return checkSum;
+    }
+
+    private static void sortByInsertionSort(Object object) {
+        if (object instanceof int[]) {
+            sortByInsertionSort((int[]) object);
+        } else if (object instanceof long[]) {
+            sortByInsertionSort((long[]) object);
+        } else if (object instanceof short[]) {
+            sortByInsertionSort((short[]) object);
+        } else if (object instanceof byte[]) {
+            sortByInsertionSort((byte[]) object);
+        } else if (object instanceof char[]) {
+            sortByInsertionSort((char[]) object);
+        } else if (object instanceof float[]) {
+            sortByInsertionSort((float[]) object);
+        } else if (object instanceof double[]) {
+            sortByInsertionSort((double[]) object);
+        } else if (object instanceof Integer[]) {
+            sortByInsertionSort((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortByInsertionSort(int[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            int ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(long[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            long ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(short[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            short ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(byte[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            byte ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(char[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            char ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(float[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            float ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(double[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            double ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sortByInsertionSort(Integer[] a) {
+        for (int j, i = 1; i < a.length; i++) {
+            Integer ai = a[i];
+            for (j = i - 1; j >= 0 && ai < a[j]; j--) {
+                a[j + 1] = a[j];
+            }
+            a[j + 1] = ai;
+        }
+    }
+
+    private static void sort(Object object) {
+        if (object instanceof int[]) {
+            Arrays.parallelSort((int[]) object);
+        } else if (object instanceof long[]) {
+            Arrays.parallelSort((long[]) object);
+        } else if (object instanceof short[]) {
+            Arrays.parallelSort((short[]) object);
+        } else if (object instanceof byte[]) {
+            Arrays.parallelSort((byte[]) object);
+        } else if (object instanceof char[]) {
+            Arrays.parallelSort((char[]) object);
+        } else if (object instanceof float[]) {
+            Arrays.parallelSort((float[]) object);
+        } else if (object instanceof double[]) {
+            Arrays.parallelSort((double[]) object);
+        } else if (object instanceof Integer[]) {
+            Arrays.parallelSort((Integer[]) object);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortSubArray(Object object, int fromIndex, int toIndex) {
+        if (object instanceof int[]) {
+            Arrays.parallelSort((int[]) object, fromIndex, toIndex);
+        } else if (object instanceof long[]) {
+            Arrays.parallelSort((long[]) object, fromIndex, toIndex);
+        } else if (object instanceof short[]) {
+            Arrays.parallelSort((short[]) object, fromIndex, toIndex);
+        } else if (object instanceof byte[]) {
+            Arrays.parallelSort((byte[]) object, fromIndex, toIndex);
+        } else if (object instanceof char[]) {
+            Arrays.parallelSort((char[]) object, fromIndex, toIndex);
+        } else if (object instanceof float[]) {
+            Arrays.parallelSort((float[]) object, fromIndex, toIndex);
+        } else if (object instanceof double[]) {
+            Arrays.parallelSort((double[]) object, fromIndex, toIndex);
+        } else if (object instanceof Integer[]) {
+            Arrays.parallelSort((Integer[]) object, fromIndex, toIndex);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
+        if (object instanceof int[]) {
+            checkSubArray((int[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof long[]) {
+            checkSubArray((long[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof short[]) {
+            checkSubArray((short[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof byte[]) {
+            checkSubArray((byte[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof char[]) {
+            checkSubArray((char[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof float[]) {
+            checkSubArray((float[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof double[]) {
+            checkSubArray((double[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof Integer[]) {
+            checkSubArray((Integer[]) object, fromIndex, toIndex, m);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i].intValue() != 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i].intValue() != 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (byte) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (byte) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (long) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (long) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (char) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (char) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (short) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (short) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (float) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (float) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (double) 0xDEDA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failedSort(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (double) 0xBABA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+    }
+
+    private static void checkRange(Object object, int m) {
+        if (object instanceof int[]) {
+            checkRange((int[]) object, m);
+        } else if (object instanceof long[]) {
+            checkRange((long[]) object, m);
+        } else if (object instanceof short[]) {
+            checkRange((short[]) object, m);
+        } else if (object instanceof byte[]) {
+            checkRange((byte[]) object, m);
+        } else if (object instanceof char[]) {
+            checkRange((char[]) object, m);
+        } else if (object instanceof float[]) {
+            checkRange((float[]) object, m);
+        } else if (object instanceof double[]) {
+            checkRange((double[]) object, m);
+        } else if (object instanceof Integer[]) {
+            checkRange((Integer[]) object, m);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkRange(Integer[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(int[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(long[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(byte[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(short[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(char[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(float[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(double[] a, int m) {
+        try {
+            Arrays.parallelSort(a, m + 1, m);
+
+            failed("ParallelSort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.parallelSort(a, -m, a.length);
+
+                failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.parallelSort(a, 0, a.length + m);
+
+                    failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void outArray(Object[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(int[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(float[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static void outArray(double[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+    }
+
+    private static class MyRandom extends Random {
+        MyRandom(long seed) {
+            super(seed);
+            mySeed = seed;
+        }
+
+        long getSeed() {
+            return mySeed;
+        }
+
+        private long mySeed;
+    }
+
+    private static String ourDescription;
+}