changeset 1867:18c2b761548a

6899694: Dual-pivot quicksort improvements Reviewed-by: jjb Contributed-by: vladimir.yaroslavskiy@sun.com, joshua.bloch@google.com
author alanb
date Wed, 11 Nov 2009 14:38:01 +0000
parents e75fc4dc0e22
children b901762bba4b
files src/share/classes/java/util/Arrays.java src/share/classes/java/util/DualPivotQuicksort.java test/java/util/Arrays/Sorting.java
diffstat 3 files changed, 1894 insertions(+), 633 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/Arrays.java	Tue Nov 10 13:09:50 2009 +0000
+++ b/src/share/classes/java/util/Arrays.java	Wed Nov 11 14:38:01 2009 +0000
@@ -57,12 +57,53 @@
     // Suppresses default constructor, ensuring non-instantiability.
     private Arrays() {}
 
-    // Sorting
+    /*
+     * Sorting of primitive type arrays.
+     */
 
     /**
      * Sorts the specified array into ascending numerical order.
      *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+     * offers O(n log(n)) performance on many data sets that cause other
+     * quicksorts to degrade to quadratic performance, and is typically
+     * faster than traditional (one-pivot) Quicksort implementations.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(int[] a) {
+        DualPivotQuicksort.sort(a);
+    }
+
+    /**
+     * 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 Dual-Pivot Quicksort
+     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+     * offers O(n log(n)) performance on many data sets that cause other
+     * quicksorts to degrade to quadratic performance, and is typically
+     * faster than traditional (one-pivot) Quicksort implementations.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(int[] a, int fromIndex, int toIndex) {
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
@@ -71,76 +112,37 @@
      * @param a the array to be sorted
      */
     public static void sort(long[] a) {
-        sort(a, 0, a.length);
+        DualPivotQuicksort.sort(a);
     }
 
     /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of to be sorted extends from the index {@code fromIndex}, inclusive,
-     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * 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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
      * faster than traditional (one-pivot) Quicksort implementations.
      *
      * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void sort(long[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
     }
 
     /**
      * Sorts the specified array into ascending numerical order.
      *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
-     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-     * offers O(n log(n)) performance on many data sets that cause other
-     * quicksorts to degrade to quadratic performance, and is typically
-     * faster than traditional (one-pivot) Quicksort implementations.
-     *
-     * @param a the array to be sorted
-     */
-    public static void sort(int[] a) {
-        sort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of 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 Dual-Pivot Quicksort,
-     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-     * offers O(n log(n)) performance on many data sets that cause other
-     * quicksorts to degrade to quadratic performance, and is typically
-     * faster than traditional (one-pivot) Quicksort implementations.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     */
-    public static void sort(int[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
-     *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
@@ -149,37 +151,37 @@
      * @param a the array to be sorted
      */
     public static void sort(short[] a) {
-        sort(a, 0, a.length);
+        DualPivotQuicksort.sort(a);
     }
 
     /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of to be sorted extends from the index {@code fromIndex}, inclusive,
-     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * 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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
      * faster than traditional (one-pivot) Quicksort implementations.
      *
      * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void sort(short[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
     }
 
     /**
      * Sorts the specified array into ascending numerical order.
      *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
@@ -188,37 +190,37 @@
      * @param a the array to be sorted
      */
     public static void sort(char[] a) {
-        sort(a, 0, a.length);
+        DualPivotQuicksort.sort(a);
     }
 
     /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of to be sorted extends from the index {@code fromIndex}, inclusive,
-     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * 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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
      * faster than traditional (one-pivot) Quicksort implementations.
      *
      * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void sort(char[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
     }
 
     /**
      * Sorts the specified array into ascending numerical order.
      *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
@@ -227,49 +229,100 @@
      * @param a the array to be sorted
      */
     public static void sort(byte[] a) {
-        sort(a, 0, a.length);
+        DualPivotQuicksort.sort(a);
     }
 
     /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of to be sorted extends from the index {@code fromIndex}, inclusive,
-     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * 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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
      * faster than traditional (one-pivot) Quicksort implementations.
      *
      * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void sort(byte[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
     }
 
     /**
      * Sorts the specified array into ascending numerical order.
      *
-     * <p>The {@code <} relation does not provide a total order on
-     * all floating-point values; although they are distinct numbers
-     * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares
-     * neither less than, greater than, nor equal to any floating-point
-     * value, even itself. To allow the sort to proceed, instead of using
-     * the {@code <} relation to determine ascending numerical order,
-     * this method uses the total order imposed by {@link Double#compareTo}.
-     * This ordering differs from the {@code <} relation in that {@code -0.0d}
-     * is treated as less than {@code 0.0d} and NaN is considered greater than
-     * any other floating-point value. For the purposes of sorting, all NaN
-     * values are considered equivalent and equal.
+     * <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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+     * offers O(n log(n)) performance on many data sets that cause other
+     * quicksorts to degrade to quadratic performance, and is typically
+     * faster than traditional (one-pivot) Quicksort implementations.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(float[] a) {
+        DualPivotQuicksort.sort(a);
+    }
+
+    /**
+     * 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 Dual-Pivot Quicksort
+     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+     * offers O(n log(n)) performance on many data sets that cause other
+     * quicksorts to degrade to quadratic performance, and is typically
+     * faster than traditional (one-pivot) Quicksort implementations.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(float[] a, int fromIndex, int toIndex) {
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
+    }
+
+    /**
+     * 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 Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
@@ -278,203 +331,45 @@
      * @param a the array to be sorted
      */
     public static void sort(double[] a) {
-        sort(a, 0, a.length);
+        DualPivotQuicksort.sort(a);
     }
 
     /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of to be sorted extends from the index {@code fromIndex}, inclusive,
-     * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+     * 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 floating-point values; although they are distinct numbers
-     * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares
-     * neither less than, greater than, nor equal to any floating-point
-     * value, even itself. To allow the sort to proceed, instead of using
-     * the {@code <} relation to determine ascending numerical order,
-     * this method uses the total order imposed by {@link Double#compareTo}.
-     * This ordering differs from the {@code <} relation in that {@code -0.0d}
-     * is treated as less than {@code 0.0d} and NaN is considered greater than
-     * any other floating-point value. For the purposes of sorting, all NaN
-     * values are considered equivalent and equal.
+     * <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 Dual-Pivot Quicksort,
+     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
      * offers O(n log(n)) performance on many data sets that cause other
      * quicksorts to degrade to quadratic performance, and is typically
      * faster than traditional (one-pivot) Quicksort implementations.
      *
      * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     *
      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
      * @throws ArrayIndexOutOfBoundsException
      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
      */
     public static void sort(double[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        sortNegZeroAndNaN(a, fromIndex, toIndex);
+        DualPivotQuicksort.sort(a, fromIndex, toIndex);
     }
 
-    private static void sortNegZeroAndNaN(double[] a, int fromIndex, int toIndex) {
-        final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
-        /*
-         * The sort is done in three phases to avoid the expense of using
-         * NaN and -0.0d aware comparisons during the main sort.
-         *
-         * Preprocessing phase: move any NaN's to end of array, count the
-         * number of -0.0d's, and turn them into 0.0d's.
-         */
-        int numNegZeros = 0;
-        int i = fromIndex;
-        int n = toIndex;
-        double temp;
-
-        while (i < n) {
-            if (a[i] != a[i]) {
-                n--;
-                temp = a[i];
-                a[i] = a[n];
-                a[n] = temp;
-            }
-            else {
-                if (a[i] == 0 && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) {
-                    a[i] = 0.0d;
-                    numNegZeros++;
-                }
-                i++;
-            }
-        }
-        // Main sort phase: quicksort everything but the NaN's
-        DualPivotQuicksort.sort(a, fromIndex, n - 1);
-
-        // Postprocessing phase: change 0.0d's to -0.0d's as required
-        if (numNegZeros != 0) {
-            int j = binarySearch0(a, fromIndex, n, 0.0d); // position of ANY zero
-
-            do {
-                j--;
-            }
-            while (j >= fromIndex && a[j] == 0.0d);
-
-            // j is now one less than the index of the FIRST zero
-            for (int k = 0; k < numNegZeros; k++) {
-                a[++j] = -0.0d;
-            }
-        }
-    }
-
-    /**
-     * Sorts the specified array into ascending numerical order.
+    /*
+     * Sorting of complex type arrays.
      *
-     * <p>The {@code <} relation does not provide a total order on
-     * all floating-point values; although they are distinct numbers
-     * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares
-     * neither less than, greater than, nor equal to any floating-point
-     * value, even itself. To allow the sort to proceed, instead of using
-     * the {@code <} relation to determine ascending numerical order,
-     * this method uses the total order imposed by {@link Float#compareTo}.
-     * This ordering differs from the {@code <} relation in that {@code -0.0f}
-     * is treated as less than {@code 0.0f} and NaN is considered greater than
-     * any other floating-point value. For the purposes of sorting, all NaN
-     * values are considered equivalent and equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
-     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-     * offers O(n log(n)) performance on many data sets that cause other
-     * quicksorts to degrade to quadratic performance, and is typically
-     * faster than traditional (one-pivot) Quicksort implementations.
-     *
-     * @param a the array to be sorted
      */
-    public static void sort(float[] a) {
-        sort(a, 0, a.length);
-    }
-
-    /**
-     * Sorts the specified range of the specified array into ascending order. The
-     * range of 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 floating-point values; although they are distinct numbers
-     * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares
-     * neither less than, greater than, nor equal to any floating-point
-     * value, even itself. To allow the sort to proceed, instead of using
-     * the {@code <} relation to determine ascending numerical order,
-     * this method uses the total order imposed by {@link Float#compareTo}.
-     * This ordering differs from the {@code <} relation in that {@code -0.0f}
-     * is treated as less than {@code 0.0f} and NaN is considered greater than
-     * any other floating-point value. For the purposes of sorting, all NaN
-     * values are considered equivalent and equal.
-     *
-     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
-     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
-     * offers O(n log(n)) performance on many data sets that cause other
-     * quicksorts to degrade to quadratic performance, and is typically
-     * faster than traditional (one-pivot) Quicksort implementations.
-     *
-     * @param a the array to be sorted
-     * @param fromIndex the index of the first element, inclusively, to be sorted
-     * @param toIndex the index of the last element, exclusively, to be sorted
-     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
-     * @throws ArrayIndexOutOfBoundsException
-     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
-     */
-    public static void sort(float[] a, int fromIndex, int toIndex) {
-        rangeCheck(a.length, fromIndex, toIndex);
-        sortNegZeroAndNaN(a, fromIndex, toIndex);
-    }
-
-    private static void sortNegZeroAndNaN(float[] a, int fromIndex, int toIndex) {
-        final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
-        /*
-         * The sort is done in three phases to avoid the expense of using
-         * NaN and -0.0f aware comparisons during the main sort.
-         *
-         * Preprocessing phase: move any NaN's to end of array, count the
-         * number of -0.0f's, and turn them into 0.0f's.
-         */
-        int numNegZeros = 0;
-        int i = fromIndex;
-        int n = toIndex;
-        float temp;
-
-        while (i < n) {
-            if (a[i] != a[i]) {
-                n--;
-                temp = a[i];
-                a[i] = a[n];
-                a[n] = temp;
-            }
-            else {
-                if (a[i] == 0 && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) {
-                    a[i] = 0.0f;
-                    numNegZeros++;
-                }
-                i++;
-            }
-        }
-        // Main sort phase: quicksort everything but the NaN's
-        DualPivotQuicksort.sort(a, fromIndex, n - 1);
-
-        // Postprocessing phase: change 0.0f's to -0.0f's as required
-        if (numNegZeros != 0) {
-            int j = binarySearch0(a, fromIndex, n, 0.0f); // position of ANY zero
-
-            do {
-                j--;
-            }
-            while (j >= fromIndex && a[j] == 0.0f);
-
-            // j is now one less than the index of the FIRST zero
-            for (int k = 0; k < numNegZeros; k++) {
-                a[++j] = -0.0f;
-            }
-        }
-    }
 
     /**
      * Old merge sort implementation can be selected (for
--- a/src/share/classes/java/util/DualPivotQuicksort.java	Tue Nov 10 13:09:50 2009 +0000
+++ b/src/share/classes/java/util/DualPivotQuicksort.java	Wed Nov 11 14:38:01 2009 +0000
@@ -36,11 +36,11 @@
  * @author Jon Bentley
  * @author Josh Bloch
  *
- * @version 2009.10.29 m765.827.v5
+ * @version 2009.11.09 m765.827.v8
  */
 final class DualPivotQuicksort {
 
-    // Suppresses default constructor, ensuring non-instantiability.
+    // Suppresses default constructor
     private DualPivotQuicksort() {}
 
     /*
@@ -70,13 +70,43 @@
      */
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * Sorts the specified array into ascending numerical order.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
      */
-    static void sort(int[] a, int left, int right) {
+    public static void sort(int[] a) {
+        doSort(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(int[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        doSort(a, fromIndex, toIndex - 1);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in that the
+     * {@code right} index is inclusive, and it does no range checking on
+     * {@code left} or {@code right}.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void doSort(int[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -94,12 +124,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(int[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -234,8 +264,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -271,17 +301,47 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
     }
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * Sorts the specified array into ascending numerical order.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
      */
-    static void sort(long[] a, int left, int right) {
+    public static void sort(long[] a) {
+        doSort(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(long[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        doSort(a, fromIndex, toIndex - 1);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in that the
+     * {@code right} index is inclusive, and it does no range checking on
+     * {@code left} or {@code right}.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void doSort(long[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -299,12 +359,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(long[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -439,8 +499,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -476,20 +536,50 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
     }
 
-    /** The number of distinct short values */
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(short[] a) {
+        doSort(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(short[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        doSort(a, fromIndex, toIndex - 1);
+    }
+
+    /** The number of distinct short values. */
     private static final int NUM_SHORT_VALUES = 1 << 16;
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in that the
+     * {@code right} index is inclusive, and it does no range checking on
+     * {@code left} or {@code right}.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
-    static void sort(short[] a, int left, int right) {
+    private static void doSort(short[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -501,7 +591,7 @@
                 }
                 a[j + 1] = ak;
             }
-        } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+        } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             // Use counting sort on huge arrays
             int[] count = new int[NUM_SHORT_VALUES];
 
@@ -521,12 +611,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(short[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -661,8 +751,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -698,20 +788,300 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
     }
 
-    /** The number of distinct byte values */
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(char[] a) {
+        doSort(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(char[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        doSort(a, fromIndex, toIndex - 1);
+    }
+
+    /** The number of distinct char values. */
+    private static final int NUM_CHAR_VALUES = 1 << 16;
+
+    /**
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in that the
+     * {@code right} index is inclusive, and it does no range checking on
+     * {@code left} or {@code right}.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void doSort(char[] a, int left, int right) {
+        // Use insertion sort on tiny arrays
+        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+            for (int k = left + 1; k <= right; k++) {
+                char ak = a[k];
+                int j;
+
+                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                    a[j + 1] = a[j];
+                }
+                a[j + 1] = ak;
+            }
+        } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+            // Use counting sort on huge arrays
+            int[] count = new int[NUM_CHAR_VALUES];
+
+            for (int i = left; i <= right; i++) {
+                count[a[i]]++;
+            }
+            for (int i = 0, k = left; i < count.length && k <= right; i++) {
+                for (int s = count[i]; s > 0; s--) {
+                    a[k++] = (char) i;
+               }
+            }
+        } else { // Use Dual-Pivot Quicksort on large arrays
+            dualPivotQuicksort(a, left, right);
+        }
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void dualPivotQuicksort(char[] a, int left, int right) {
+        // Compute indices of five evenly spaced elements
+        int sixth = (right - left + 1) / 6;
+        int e1 = left  + sixth;
+        int e5 = right - sixth;
+        int e3 = (left + right) >>> 1; // The midpoint
+        int e4 = e3 + sixth;
+        int e2 = e3 - sixth;
+
+        // Sort these elements in place using a 5-element sorting network
+        if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
+        if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
+        if (a[e1] > a[e3]) { char t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
+        if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
+        if (a[e1] > a[e4]) { char t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
+        if (a[e3] > a[e4]) { char t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
+        if (a[e2] > a[e5]) { char t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
+        if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
+        if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
+
+        /*
+         * Use the second and fourth of the five sorted elements as pivots.
+         * These values are inexpensive approximations of the first and
+         * second terciles of the array. Note that pivot1 <= pivot2.
+         *
+         * The pivots are stored in local variables, and the first and
+         * the last of the sorted elements are moved to the locations
+         * formerly occupied by the pivots. When partitioning is complete,
+         * the pivots are swapped back into their final positions, and
+         * excluded from subsequent sorting.
+         */
+        char pivot1 = a[e2]; a[e2] = a[left];
+        char pivot2 = a[e4]; a[e4] = a[right];
+
+        /*
+         * Partitioning
+         *
+         *   left part         center part                  right part
+         * ------------------------------------------------------------
+         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
+         * ------------------------------------------------------------
+         *              ^                          ^     ^
+         *              |                          |     |
+         *             less                        k   great
+         */
+
+        // Pointers
+        int less  = left  + 1; // The index of first element of center part
+        int great = right - 1; // The index before first element of right part
+
+        boolean pivotsDiffer = pivot1 != pivot2;
+
+        if (pivotsDiffer) {
+            /*
+             * Invariants:
+             *              all in (left, less)   < pivot1
+             *    pivot1 <= all in [less, k)     <= pivot2
+             *              all in (great, right) > pivot2
+             *
+             * Pointer k is the first index of ?-part
+             */
+            for (int k = less; k <= great; k++) {
+                char ak = a[k];
+
+                if (ak < pivot1) {
+                    a[k] = a[less];
+                    a[less++] = ak;
+                } else if (ak > pivot2) {
+                    while (a[great] > pivot2 && k < great) {
+                        great--;
+                    }
+                    a[k] = a[great];
+                    a[great--] = ak;
+                    ak = a[k];
+
+                    if (ak < pivot1) {
+                        a[k] = a[less];
+                        a[less++] = ak;
+                    }
+                }
+            }
+        } else { // Pivots are equal
+            /*
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") partition:
+             *
+             *   left part   center part            right part
+             * -------------------------------------------------
+             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+             * -------------------------------------------------
+             *
+             *              ^            ^       ^
+             *              |            |       |
+             *             less          k     great
+             *
+             * Invariants:
+             *
+             *   all in (left, less)   < pivot
+             *   all in [less, k)     == pivot
+             *   all in (great, right) > pivot
+             *
+             * Pointer k is the first index of ?-part
+             */
+            for (int k = less; k <= great; k++) {
+                char ak = a[k];
+
+                if (ak == pivot1) {
+                  continue;
+                }
+                if (ak < pivot1) {
+                    a[k] = a[less];
+                    a[less++] = ak;
+                } else {
+                    while (a[great] > pivot1) {
+                        great--;
+                    }
+                    a[k] = a[great];
+                    a[great--] = ak;
+                    ak = a[k];
+
+                    if (ak < pivot1) {
+                        a[k] = a[less];
+                        a[less++] = ak;
+                    }
+                }
+            }
+        }
+
+        // Swap pivots into their final positions
+        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+        a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+        // Sort left and right parts recursively, excluding known pivot values
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
+
+        /*
+         * If pivot1 == pivot2, all elements from center
+         * part are equal and, therefore, already sorted
+         */
+        if (!pivotsDiffer) {
+            return;
+        }
+
+        /*
+         * If center part is too large (comprises > 5/6 of
+         * the array), swap internal pivot values to ends
+         */
+        if (less < e1 && e5 < great) {
+            while (a[less] == pivot1) {
+                less++;
+            }
+            for (int k = less + 1; k <= great; k++) {
+                if (a[k] == pivot1) {
+                    a[k] = a[less];
+                    a[less++] = pivot1;
+                }
+            }
+            while (a[great] == pivot2) {
+                great--;
+            }
+            for (int k = great - 1; k >= less; k--) {
+                if (a[k] == pivot2) {
+                    a[k] = a[great];
+                    a[great--] = pivot2;
+                }
+            }
+        }
+
+        // Sort center part recursively, excluding known pivot values
+        doSort(a, less, great);
+    }
+
+    /**
+     * Sorts the specified array into ascending numerical order.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(byte[] a) {
+        doSort(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(byte[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        doSort(a, fromIndex, toIndex - 1);
+    }
+
+    /** The number of distinct byte values. */
     private static final int NUM_BYTE_VALUES = 1 << 8;
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in that the
+     * {@code right} index is inclusive, and it does no range checking on
+     * {@code left} or {@code right}.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
-    static void sort(byte[] a, int left, int right) {
+    private static void doSort(byte[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -743,12 +1113,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(byte[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -883,8 +1253,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -920,237 +1290,143 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
     }
 
-    /** The number of distinct char values */
-    private static final int NUM_CHAR_VALUES = 1 << 16;
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     */
+    public static void sort(float[] a) {
+        sortNegZeroAndNaN(a, 0, a.length - 1);
+    }
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * 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.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, 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}
      */
-    static void sort(char[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int k = left + 1; k <= right; k++) {
-                char ak = a[k];
-                int j;
+    public static void sort(float[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
+    }
 
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ak;
+    /**
+     * Sorts the specified range of the array into ascending order. The
+     * sort is done in three phases to avoid expensive comparisons in the
+     * inner loop. The comparisons would be expensive due to anomalies
+     * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void sortNegZeroAndNaN(float[] a, int left, int right) {
+        /*
+         * Phase 1: Count negative zeros and move NaNs to end of array
+         */
+        final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+        int numNegativeZeros = 0;
+        int n = right;
+
+        for (int k = left; k <= n; k++) {
+            float ak = a[k];
+
+            if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
+                a[k] = 0.0f;
+                numNegativeZeros++;
+            } else if (ak != ak) { // i.e., ak is NaN
+                a[k--] = a[n];
+                a[n--] = Float.NaN;
             }
-        } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
-            // Use counting sort on huge arrays
-            int[] count = new int[NUM_CHAR_VALUES];
+        }
 
-            for (int i = left; i <= right; i++) {
-                count[a[i]]++;
-            }
-            for (int i = 0, k = left; i < count.length && k <= right; i++) {
-                for (int s = count[i]; s > 0; s--) {
-                    a[k++] = (char) i;
-               }
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+        /*
+         * Phase 2: Sort everything except NaNs (which are already in place)
+         */
+        doSort(a, left, n);
+
+        /*
+         * Phase 3: Turn positive zeros back into negative zeros as appropriate
+         */
+        if (numNegativeZeros == 0) {
+            return;
+        }
+
+        // Find first zero element
+        int zeroIndex = findAnyZero(a, left, n);
+
+        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
+            zeroIndex = i;
+        }
+
+        // Turn the right number of positive zeros back into negative zeros
+        for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+            a[i] = -0.0f;
         }
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Returns the index of some zero element in the specified range via
+     * binary search. The range is assumed to be sorted, and must contain
+     * at least one zero.
      *
-     * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param a the array to be searched
+     * @param low the index of the first element, inclusive, to be searched
+     * @param high the index of the last element, inclusive, to be searched
      */
-    private static void dualPivotQuicksort(char[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
-        int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+    private static int findAnyZero(float[] a, int low, int high) {
+        while (true) {
+            int middle = (low + high) >>> 1;
+            float middleValue = a[middle];
 
-        // Sort these elements in place using a 5-element sorting network
-        if (a[e1] > a[e2]) { char t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
-        if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
-        if (a[e1] > a[e3]) { char t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
-        if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
-        if (a[e1] > a[e4]) { char t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
-        if (a[e3] > a[e4]) { char t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
-        if (a[e2] > a[e5]) { char t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
-        if (a[e2] > a[e3]) { char t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
-        if (a[e4] > a[e5]) { char t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
-
-        /*
-         * Use the second and fourth of the five sorted elements as pivots.
-         * These values are inexpensive approximations of the first and
-         * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
-         */
-        char pivot1 = a[e2]; a[e2] = a[left];
-        char pivot2 = a[e4]; a[e4] = a[right];
-
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
-        // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
-
-        boolean pivotsDiffer = pivot1 != pivot2;
-
-        if (pivotsDiffer) {
-            /*
-             * Invariants:
-             *              all in (left, less)   < pivot1
-             *    pivot1 <= all in [less, k)     <= pivot2
-             *              all in (great, right) > pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            for (int k = less; k <= great; k++) {
-                char ak = a[k];
-
-                if (ak < pivot1) {
-                    a[k] = a[less];
-                    a[less++] = ak;
-                } else if (ak > pivot2) {
-                    while (a[great] > pivot2 && k < great) {
-                        great--;
-                    }
-                    a[k] = a[great];
-                    a[great--] = ak;
-                    ak = a[k];
-
-                    if (ak < pivot1) {
-                        a[k] = a[less];
-                        a[less++] = ak;
-                    }
-                }
-            }
-        } else { // Pivots are equal
-            /*
-             * Partition degenerates to the traditional 3-way
-             * (or "Dutch National Flag") partition:
-             *
-             *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
-             *
-             * Invariants:
-             *
-             *   all in (left, less)   < pivot
-             *   all in [less, k)     == pivot
-             *   all in (great, right) > pivot
-             *
-             * Pointer k is the first index of ?-part
-             */
-            for (int k = less; k <= great; k++) {
-                char ak = a[k];
-
-                if (ak == pivot1) {
-                  continue;
-                }
-                if (ak < pivot1) {
-                    a[k] = a[less];
-                    a[less++] = ak;
-                } else {
-                    while (a[great] > pivot1) {
-                        great--;
-                    }
-                    a[k] = a[great];
-                    a[great--] = ak;
-                    ak = a[k];
-
-                    if (ak < pivot1) {
-                        a[k] = a[less];
-                        a[less++] = ak;
-                    }
-                }
+            if (middleValue < 0.0f) {
+                low = middle + 1;
+            } else if (middleValue > 0.0f) {
+                high = middle - 1;
+            } else { // middleValue == 0.0f
+                return middle;
             }
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
-         */
-        if (less < e1 && e5 < great) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            for (int k = less + 1; k <= great; k++) {
-                if (a[k] == pivot1) {
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-            for (int k = great - 1; k >= less; k--) {
-                if (a[k] == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
     }
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in three ways:
+     * {@code right} index is inclusive, it does no range checking on
+     * {@code left} or {@code right}, and it does not handle negative
+     * zeros or NaNs in the array.
      *
-     * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param a the array to be sorted, which must not contain -0.0f or NaN
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
-    static void sort(float[] a, int left, int right) {
+    private static void doSort(float[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -1168,12 +1444,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(float[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -1308,8 +1584,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -1345,17 +1621,143 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
     }
 
     /**
-     * Sorts the specified range of the array into ascending order.
+     * 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.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
      */
-    static void sort(double[] a, int left, int right) {
+    public static void sort(double[] a) {
+        sortNegZeroAndNaN(a, 0, a.length - 1);
+    }
+
+    /**
+     * 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.
+     *
+     * @param a the array to be sorted
+     * @param fromIndex the index of the first element, inclusive, to be sorted
+     * @param toIndex the index of the last element, exclusive, to be sorted
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > a.length}
+     */
+    public static void sort(double[] a, int fromIndex, int toIndex) {
+        rangeCheck(a.length, fromIndex, toIndex);
+        sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. The
+     * sort is done in three phases to avoid expensive comparisons in the
+     * inner loop. The comparisons would be expensive due to anomalies
+     * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
+     *
+     * @param a the array to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void sortNegZeroAndNaN(double[] a, int left, int right) {
+        /*
+         * Phase 1: Count negative zeros and move NaNs to end of array
+         */
+        final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+        int numNegativeZeros = 0;
+        int n = right;
+
+        for (int k = left; k <= n; k++) {
+            double ak = a[k];
+
+            if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
+                a[k] = 0.0d;
+                numNegativeZeros++;
+            } else if (ak != ak) { // i.e., ak is NaN
+                a[k--] = a[n];
+                a[n--] = Double.NaN;
+            }
+        }
+
+        /*
+         * Phase 2: Sort everything except NaNs (which are already in place)
+         */
+        doSort(a, left, n);
+
+        /*
+         * Phase 3: Turn positive zeros back into negative zeros as appropriate
+         */
+        if (numNegativeZeros == 0) {
+            return;
+        }
+
+        // Find first zero element
+        int zeroIndex = findAnyZero(a, left, n);
+
+        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
+            zeroIndex = i;
+        }
+
+        // Turn the right number of positive zeros back into negative zeros
+        for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+            a[i] = -0.0d;
+        }
+    }
+
+    /**
+     * Returns the index of some zero element in the specified range via
+     * binary search. The range is assumed to be sorted, and must contain
+     * at least one zero.
+     *
+     * @param a the array to be searched
+     * @param low the index of the first element, inclusive, to be searched
+     * @param high the index of the last element, inclusive, to be searched
+     */
+    private static int findAnyZero(double[] a, int low, int high) {
+        while (true) {
+            int middle = (low + high) >>> 1;
+            double middleValue = a[middle];
+
+            if (middleValue < 0.0d) {
+                low = middle + 1;
+            } else if (middleValue > 0.0d) {
+                high = middle - 1;
+            } else { // middleValue == 0.0d
+                return middle;
+            }
+        }
+    }
+
+    /**
+     * Sorts the specified range of the array into ascending order. This
+     * method differs from the public {@code sort} method in three ways:
+     * {@code right} index is inclusive, it does no range checking on
+     * {@code left} or {@code right}, and it does not handle negative
+     * zeros or NaNs in the array.
+     *
+     * @param a the array to be sorted, which must not contain -0.0d and NaN
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
+     */
+    private static void doSort(double[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
             for (int k = left + 1; k <= right; k++) {
@@ -1373,12 +1775,12 @@
     }
 
     /**
-     * Sorts the specified range of the array into ascending order
-     * by Dual-Pivot Quicksort.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm.
      *
      * @param a the array to be sorted
-     * @param left the index of the first element, inclusively, to be sorted
-     * @param right the index of the last element, inclusively, to be sorted
+     * @param left the index of the first element, inclusive, to be sorted
+     * @param right the index of the last element, inclusive, to be sorted
      */
     private static void dualPivotQuicksort(double[] a, int left, int right) {
         // Compute indices of five evenly spaced elements
@@ -1513,8 +1915,8 @@
         a[right] = a[great + 1]; a[great + 1] = pivot2;
 
         // Sort left and right parts recursively, excluding known pivot values
-        sort(a, left,   less - 2);
-        sort(a, great + 2, right);
+        doSort(a, left,   less - 2);
+        doSort(a, great + 2, right);
 
         /*
          * If pivot1 == pivot2, all elements from center
@@ -1550,6 +1952,23 @@
         }
 
         // Sort center part recursively, excluding known pivot values
-        sort(a, less, great);
+        doSort(a, less, great);
+    }
+
+    /**
+     * Checks that {@code fromIndex} and {@code toIndex} are in
+     * the range and throws an appropriate exception, if they aren't.
+     */
+    private static void rangeCheck(int length, int fromIndex, int toIndex) {
+        if (fromIndex > toIndex) {
+            throw new IllegalArgumentException(
+                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+        }
+        if (fromIndex < 0) {
+            throw new ArrayIndexOutOfBoundsException(fromIndex);
+        }
+        if (toIndex > length) {
+            throw new ArrayIndexOutOfBoundsException(toIndex);
+        }
     }
 }
--- a/test/java/util/Arrays/Sorting.java	Tue Nov 10 13:09:50 2009 +0000
+++ b/test/java/util/Arrays/Sorting.java	Wed Nov 11 14:38:01 2009 +0000
@@ -23,11 +23,14 @@
 
 /*
  * @test
- * @bug 6880672 6896573
+ * @bug 6880672 6896573 6899694
  * @summary Exercise Arrays.sort
  * @build Sorting
  * @run main Sorting -shortrun
- * @author Vladimir Yaroslavskiy, Josh Bloch, Jon Bentley
+ *
+ * @author Vladimir Yaroslavskiy
+ * @author Jon Bentley
+ * @author Josh Bloch
  */
 
 import java.util.Arrays;
@@ -35,59 +38,300 @@
 import java.io.PrintStream;
 
 public class Sorting {
-    static final PrintStream out = System.out;
-    static final PrintStream err = System.err;
+    private static final PrintStream out = System.out;
+    private static final PrintStream err = System.err;
 
-    // array lengths used in a long run (default)
-    static final int[] LONG_RUN = {
-        0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};
+    // 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
-    static final int[] SHORT_RUN = {0, 1, 2, 3, 21, 55, 1000, 10000, 500000};
+    // 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 = false;
-        if (args.length > 0 && args[0].equals("-shortrun"))
-            shortRun = true;
+        boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
+        long start = System.currentTimeMillis();
 
-        long start = System.nanoTime();
+        if (shortRun) {
+            testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
+        } else {
+            testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
+        }
+        long end = System.currentTimeMillis();
 
-        testAndCheck((shortRun) ? SHORT_RUN : LONG_RUN);
-
-        long end = System.nanoTime();
-
-        out.println();
-        out.format("PASS in %ds%n", Math.round((end - start) / 1e9));
+        out.format("PASS in %d sec.\n", Math.round((end - start) / 1E3));
     }
 
-    static void testAndCheck(int[] lengths) {
-        for (int len : lengths) {
-            out.println();
-            ArrayBuilder.reset();
-            int[] golden = new int[len];
+    private static void testAndCheck(int[] lengths, long[] randoms) {
+        for (long random : randoms) {
+            reset(random);
 
-            for (int m = 1; m < 2 * len; m *= 2) {
-                for (ArrayBuilder builder : ArrayBuilder.values()) {
-                    builder.build(golden, m);
-                    int[] test = golden.clone();
+            for (int len : lengths) {
+                testAndCheckWithCheckSum(len, random);
+            }
+            reset(random);
 
-                    for (Converter converter : Converter.values()) {
-                        out.println("Test: " + converter + " " + builder +
-                            "len = " + len + ", m = " + m);
-                        Object convertedGolden = converter.convert(golden);
-                        Object convertedTest = converter.convert(test);
-                        sort(convertedTest);
-                        checkWithCheckSum(convertedTest, convertedGolden);
+            for (int len : lengths) {
+                testAndCheckWithScrambling(len, random);
+            }
+            reset(random);
+
+            for (int len : lengths) {
+                testAndCheckFloat(len, random);
+            }
+            reset(random);
+
+            for (int len : lengths) {
+                testAndCheckDouble(len, random);
+            }
+            reset(random);
+
+            for (int len : lengths) {
+                testAndCheckRange(len, random);
+            }
+            reset(random);
+
+            for (int len : lengths) {
+                testAndCheckSubArray(len, random);
+            }
+        }
+    }
+
+    private static void testAndCheckSubArray(int len, long random) {
+        int[] golden = new int[len];
+
+        for (int m = 1; m < len / 2; m *= 2) {
+            int fromIndex = m;
+            int toIndex = len - m;
+
+            prepareSubArray(golden, fromIndex, toIndex, m);
+            int[] test = golden.clone();
+
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test #6: " + converter +
+                   " len = " + len + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                Object convertedTest = converter.convert(test);
+
+                // outArr(test);
+                sortSubArray(convertedTest, fromIndex, toIndex);
+                // outArr(test);
+                checkSubArray(convertedTest, fromIndex, toIndex, m);
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckRange(int len, long random) {
+        int[] golden = new int[len];
+
+        for (int m = 1; m < 2 * len; m *= 2) {
+            for (int i = 1; i <= len; i++) {
+                golden[i - 1] = i % m + m % i;
+            }
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test #5: " + converter +
+                   ", len = " + len + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                sortRange(convertedGolden, m);
+                sortEmpty(convertedGolden);
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithCheckSum(int len, long random) {
+        int[] golden = new int[len];
+
+        for (int m = 1; m < 2 * len; m *= 2) {
+            for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test #1: " + converter + " " + builder +
+                       "random = " +  random + ", len = " + len +
+                       ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    checkWithCheckSum(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithScrambling(int len, long random) {
+        int[] golden = new int[len];
+
+        for (int m = 1; m <= 7; m++) {
+            if (m > len) {
+                break;
+            }
+            for (SortedBuilder builder : SortedBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+                scramble(test);
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test #2: " + converter + " " + builder +
+                       "random = " +  random + ", len = " + len +
+                       ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    Object convertedTest = converter.convert(test);
+                    sort(convertedTest);
+                    compare(convertedTest, convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckFloat(int len, long random) {
+        float[] golden = new float[len];
+        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 > len) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < len) {
+                                continue;
+                            }
+                            for (FloatBuilder builder : FloatBuilder.values()) {
+                                out.println("Test #3: random = " + random +
+                                   ", len = " + len + ", a = " + a + ", g = " + g +
+                                   ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p);
+                                float[] test = golden.clone();
+                                scramble(test);
+                                // outArr(test);
+                                sort(test);
+                                // outArr(test);
+                                compare(test, golden, a, n, g);
+                            }
+                            newLine = true;
+                        }
                     }
                 }
             }
         }
+        if (newLine) {
+            out.println();
+        }
     }
 
-    static enum Converter {
+    private static void testAndCheckDouble(int len, long random) {
+        double[] golden = new double[len];
+        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 > len) {
+                                continue;
+                            }
+                            if (a + g + z + n + p < len) {
+                                continue;
+                            }
+                            for (DoubleBuilder builder : DoubleBuilder.values()) {
+                                out.println("Test #4: random = " + random +
+                                   ", len = " + len + ", a = " + a + ", g = " + g +
+                                   ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p);
+                                double[] test = golden.clone();
+                                scramble(test);
+                                // outArr(test);
+                                sort(test);
+                                // outArr(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] = 0xBABA;
+        }
+
+        for (int i = fromIndex; i < toIndex; i++) {
+            a[i] = -i + m;
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            a[i] = 0xDEDA;
+        }
+    }
+
+    private static void scramble(int[] a) {
+        int length = a.length;
+
+        for (int i = 0; i < length * 7; i++) {
+            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+        }
+    }
+
+    private static void scramble(float[] a) {
+        int length = a.length;
+
+        for (int i = 0; i < length * 7; i++) {
+            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+        }
+    }
+
+    private static void scramble(double[] a) {
+        int length = a.length;
+
+        for (int i = 0; i < length * 7; i++) {
+            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(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;
+                return a.clone();
             }
         },
         LONG {
@@ -95,7 +339,7 @@
                 long[] b = new long[a.length];
 
                 for (int i = 0; i < a.length; i++) {
-                    b[i] = (int) a[i];
+                    b[i] = (long) a[i];
                 }
                 return b;
             }
@@ -163,7 +407,161 @@
         }
     }
 
-    static enum ArrayBuilder {
+    private static enum FloatBuilder {
+        SIMPLE {
+            void build(float[] x, int a, int g, int z, int n, int p) {
+                int fromIndex = 0;
+                float negativeValue = -ourRandom.nextFloat();
+                float positiveValue =  ourRandom.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);
+    }
+
+    private static enum DoubleBuilder {
+        SIMPLE {
+            void build(double[] x, int a, int g, int z, int n, int p) {
+                int fromIndex = 0;
+                double negativeValue = -ourRandom.nextFloat();
+                double positiveValue =  ourRandom.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);
+    }
+
+    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.0f instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failed(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.0d instead of " + a[i]);
+            }
+        }
+        for (int i = 0; i < a.length - numNaN; i++) {
+            if (a[i] != b[i]) {
+                failed(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 UnsortedBuilder {
         RANDOM {
             void build(int[] a, int m) {
                 for (int i = 0; i < a.length; i++) {
@@ -268,41 +666,53 @@
 
         abstract void build(int[] a, int m);
 
-        static void reset() {
-            ourRandom = new Random(666);
-            ourFirst = 0;
-            ourSecond = 0;
-        }
-
         @Override public String toString() {
             String name = name();
+
             for (int i = name.length(); i < 12; i++) {
                 name += " ";
             }
             return name;
         }
-
-        private static int ourFirst;
-        private static int ourSecond;
-        private static Random ourRandom = new Random(666);
     }
 
-    static void checkWithCheckSum(Object test, Object golden) {
+    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 {
+            failed("Unknow type of array: " + test + " of class " +
+                test.getClass().getName());
+        }
+    }
+
+    private static void checkWithCheckSum(Object test, Object golden) {
         checkSorted(test);
         checkCheckSum(test, golden);
     }
 
-    static void failed(String message) {
-        err.format("***FAILED: %s%%n", message);
+    private static void failed(String message) {
+        err.format("\n*** FAILED: %s\n\n", message);
         throw new RuntimeException("Test failed - see log file for details");
     }
 
-    static void failed(int index, String value1, String value2) {
+    private static void failed(int index, String value1, String value2) {
         failed("Array is not sorted at " + index + "-th position: " + value1 +
                " and " + value2);
     }
 
-    static void checkSorted(Object object) {
+    private static void checkSorted(Object object) {
         if (object instanceof int[]) {
             checkSorted((int[]) object);
         } else if (object instanceof long[]) {
@@ -323,7 +733,63 @@
         }
     }
 
-    static void checkSorted(int[] a) {
+    private static void compare(int[] a, int[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i] != b[i]) {
+                failed(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]) {
+                failed(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]) {
+                failed(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]) {
+                failed(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]) {
+                failed(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]) {
+                failed(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]) {
+                failed(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
+    private static void checkSorted(int[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -331,7 +797,7 @@
         }
     }
 
-    static void checkSorted(long[] a) {
+    private static void checkSorted(long[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -339,7 +805,7 @@
         }
     }
 
-    static void checkSorted(short[] a) {
+    private static void checkSorted(short[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -347,7 +813,7 @@
         }
     }
 
-    static void checkSorted(byte[] a) {
+    private static void checkSorted(byte[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -355,7 +821,7 @@
         }
     }
 
-    static void checkSorted(char[] a) {
+    private static void checkSorted(char[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -363,7 +829,7 @@
         }
     }
 
-    static void checkSorted(float[] a) {
+    private static void checkSorted(float[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -371,7 +837,7 @@
         }
     }
 
-    static void checkSorted(double[] a) {
+    private static void checkSorted(double[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
                 failed(i, "" + a[i], "" + a[i + 1]);
@@ -379,13 +845,13 @@
         }
     }
 
-    static void checkCheckSum(Object test, Object golden) {
+    private static void checkCheckSum(Object test, Object golden) {
         if (checkSum(test) != checkSum(golden)) {
             failed("Original and sorted arrays seems not identical");
         }
     }
 
-    static int checkSum(Object object) {
+    private static int checkSum(Object object) {
         if (object instanceof int[]) {
             return checkSum((int[]) object);
         } else if (object instanceof long[]) {
@@ -407,70 +873,70 @@
         }
     }
 
-    static int checkSum(int[] a) {
-        int checkSum = 0;
+    private static int checkSum(int[] a) {
+        int checkXorSum = 0;
 
         for (int e : a) {
-            checkSum ^= e; // xor
+            checkXorSum ^= e;
         }
-        return checkSum;
+        return checkXorSum;
     }
 
-    static int checkSum(long[] a) {
-        long checkSum = 0;
+    private static int checkSum(long[] a) {
+        long checkXorSum = 0;
 
         for (long e : a) {
-            checkSum ^= e; // xor
+            checkXorSum ^= e;
         }
-        return (int) checkSum;
+        return (int) checkXorSum;
     }
 
-    static int checkSum(short[] a) {
-        short checkSum = 0;
+    private static int checkSum(short[] a) {
+        short checkXorSum = 0;
 
         for (short e : a) {
-            checkSum ^= e; // xor
+            checkXorSum ^= e;
         }
-        return (int) checkSum;
+        return (int) checkXorSum;
     }
 
-    static int checkSum(byte[] a) {
-        byte checkSum = 0;
+    private static int checkSum(byte[] a) {
+        byte checkXorSum = 0;
 
         for (byte e : a) {
-            checkSum ^= e; // xor
+            checkXorSum ^= e;
         }
-        return (int) checkSum;
+        return (int) checkXorSum;
     }
 
-    static int checkSum(char[] a) {
-        char checkSum = 0;
+    private static int checkSum(char[] a) {
+        char checkXorSum = 0;
 
         for (char e : a) {
-            checkSum ^= e; // xor
+            checkXorSum ^= e;
         }
-        return (int) checkSum;
+        return (int) checkXorSum;
     }
 
-    static int checkSum(float[] a) {
-        int checkSum = 0;
+    private static int checkSum(float[] a) {
+        int checkXorSum = 0;
 
         for (float e : a) {
-            checkSum ^= (int) e; // xor
+            checkXorSum ^= (int) e;
         }
-        return checkSum;
+        return checkXorSum;
     }
 
-    static int checkSum(double[] a) {
-        int checkSum = 0;
+    private static int checkSum(double[] a) {
+        int checkXorSum = 0;
 
         for (double e : a) {
-            checkSum ^= (int) e; // xor
+            checkXorSum ^= (int) e;
         }
-        return checkSum;
+        return checkXorSum;
     }
 
-    static void sort(Object object) {
+    private static void sort(Object object) {
         if (object instanceof int[]) {
             Arrays.sort((int[]) object);
         } else if (object instanceof long[]) {
@@ -490,4 +956,485 @@
                 object.getClass().getName());
         }
     }
+
+    private static void sortSubArray(Object object, int fromIndex, int toIndex) {
+        if (object instanceof int[]) {
+            Arrays.sort((int[]) object, fromIndex, toIndex);
+        } else if (object instanceof long[]) {
+            Arrays.sort((long[]) object, fromIndex, toIndex);
+        } else if (object instanceof short[]) {
+            Arrays.sort((short[]) object, fromIndex, toIndex);
+        } else if (object instanceof byte[]) {
+            Arrays.sort((byte[]) object, fromIndex, toIndex);
+        } else if (object instanceof char[]) {
+            Arrays.sort((char[]) object, fromIndex, toIndex);
+        } else if (object instanceof float[]) {
+            Arrays.sort((float[]) object, fromIndex, toIndex);
+        } else if (object instanceof double[]) {
+            Arrays.sort((double[]) 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 {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (byte) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (byte) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (long) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (long) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (char) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (char) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (short) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (short) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (float) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (float) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i] != (double) 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i] > a[i + 1]) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i] != (double) 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
+    private static void sortRange(Object object, int m) {
+        if (object instanceof int[]) {
+            sortRange((int[]) object, m);
+        } else if (object instanceof long[]) {
+            sortRange((long[]) object, m);
+        } else if (object instanceof short[]) {
+            sortRange((short[]) object, m);
+        } else if (object instanceof byte[]) {
+            sortRange((byte[]) object, m);
+        } else if (object instanceof char[]) {
+            sortRange((char[]) object, m);
+        } else if (object instanceof float[]) {
+            sortRange((float[]) object, m);
+        } else if (object instanceof double[]) {
+            sortRange((double[]) object, m);
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortEmpty(Object object) {
+        if (object instanceof int[]) {
+            Arrays.sort(new int [] {});
+        } else if (object instanceof long[]) {
+            Arrays.sort(new long [] {});
+        } else if (object instanceof short[]) {
+            Arrays.sort(new short [] {});
+        } else if (object instanceof byte[]) {
+            Arrays.sort(new byte [] {});
+        } else if (object instanceof char[]) {
+            Arrays.sort(new char [] {});
+        } else if (object instanceof float[]) {
+            Arrays.sort(new float [] {});
+        } else if (object instanceof double[]) {
+            Arrays.sort(new double [] {});
+        } else {
+            failed("Unknow type of array: " + object + " of class " +
+                object.getClass().getName());
+        }
+    }
+
+    private static void sortRange(int[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(long[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(byte[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(short[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(char[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(float[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void sortRange(double[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void prepareRandom(int[] a) {
+        for (int i = 0; i < a.length; i++) {
+            a[i] = ourRandom.nextInt();
+        }
+    }
+
+    private static void reset(long seed) {
+        ourRandom = new Random(seed);
+        ourFirst = 0;
+        ourSecond = 0;
+    }
+
+    private static void outArr(int[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+        out.println();
+    }
+
+    private static void outArr(float[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+        out.println();
+    }
+
+    private static void outArr(double[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
+        out.println();
+        out.println();
+    }
+
+    private static int ourFirst;
+    private static int ourSecond;
+    private static Random ourRandom;
 }