--- a/jdk/src/share/classes/java/util/DualPivotQuicksort.java Wed Jun 30 16:11:32 2010 -0700
+++ b/jdk/src/share/classes/java/util/DualPivotQuicksort.java Thu Jul 01 16:28:08 2010 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -27,7 +27,7 @@
/**
* This class implements the Dual-Pivot Quicksort algorithm by
- * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
+ * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The 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.
@@ -36,7 +36,8 @@
* @author Jon Bentley
* @author Josh Bloch
*
- * @version 2009.11.29 m765.827.12i
+ * @version 2010.06.21 m765.827.12i:5\7
+ * @since 1.7
*/
final class DualPivotQuicksort {
@@ -68,7 +69,7 @@
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
/*
- * Sorting methods for 7 primitive types.
+ * Sorting methods for seven primitive types.
*/
/**
@@ -77,7 +78,7 @@
* @param a the array to be sorted
*/
public static void sort(int[] a) {
- doSort(a, 0, a.length - 1);
+ sort(a, 0, a.length - 1, true);
}
/**
@@ -95,98 +96,132 @@
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- doSort(a, fromIndex, toIndex - 1);
+ sort(a, fromIndex, toIndex - 1, true);
}
/**
- * 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}.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
*/
- 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 i = left + 1; i <= right; i++) {
- int ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } else { // Use Dual-Pivot Quicksort on large arrays
- dualPivotQuicksort(a, left, right);
- }
- }
+ private static void sort(int[] a, int left, int right, boolean leftmost) {
+ int length = right - left + 1;
- /**
- * 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(int[] 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;
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ int ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ int ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
+
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
int e3 = (left + right) >>> 1; // The midpoint
- int e4 = e3 + sixth;
- int e2 = e3 - sixth;
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
- // Sort these elements using a 5-element sorting network
- int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
- if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
-
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- int pivot1 = ae2; a[e2] = a[left];
- int pivot2 = ae4; a[e4] = a[right];
+ int pivot1 = a[e2];
+ int pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -194,16 +229,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -213,26 +246,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ int ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1;
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -240,20 +354,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- int ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ int ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -261,92 +374,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
a[k] = pivot1;
- a[great--] = ak;
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- int ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -355,7 +409,7 @@
* @param a the array to be sorted
*/
public static void sort(long[] a) {
- doSort(a, 0, a.length - 1);
+ sort(a, 0, a.length - 1, true);
}
/**
@@ -373,98 +427,132 @@
*/
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- doSort(a, fromIndex, toIndex - 1);
+ sort(a, fromIndex, toIndex - 1, true);
}
/**
- * 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}.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
*/
- 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 i = left + 1; i <= right; i++) {
- long ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } else { // Use Dual-Pivot Quicksort on large arrays
- dualPivotQuicksort(a, left, right);
- }
- }
+ private static void sort(long[] a, int left, int right, boolean leftmost) {
+ int length = right - left + 1;
- /**
- * 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(long[] 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;
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ long ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ long ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
+
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
int e3 = (left + right) >>> 1; // The midpoint
- int e4 = e3 + sixth;
- int e2 = e3 - sixth;
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
- // Sort these elements using a 5-element sorting network
- long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
- if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
-
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- long pivot1 = ae2; a[e2] = a[left];
- long pivot2 = ae4; a[e4] = a[right];
+ long pivot1 = a[e2];
+ long pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -472,16 +560,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
long ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -491,26 +577,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ long ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1;
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -518,20 +685,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- long ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ long ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -539,92 +705,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
a[k] = pivot1;
- a[great--] = ak;
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- long ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -633,7 +740,11 @@
* @param a the array to be sorted
*/
public static void sort(short[] a) {
- doSort(a, 0, a.length - 1);
+ if (a.length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ countingSort(a, 0, a.length - 1);
+ } else {
+ sort(a, 0, a.length - 1, true);
+ }
}
/**
@@ -651,115 +762,166 @@
*/
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- doSort(a, fromIndex, toIndex - 1);
+
+ if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ countingSort(a, fromIndex, toIndex - 1);
+ } else {
+ sort(a, fromIndex, toIndex - 1, true);
+ }
}
/** 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. 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(short[] a, int left, int right) {
- // Use insertion sort on tiny arrays
- if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
- for (int i = left + 1; i <= right; i++) {
- short ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } 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];
-
- for (int i = left; i <= right; i++) {
- count[a[i] - Short.MIN_VALUE]++;
- }
- for (int i = 0, k = left; i < count.length && k <= right; i++) {
- short value = (short) (i + Short.MIN_VALUE);
-
- for (int s = count[i]; s > 0; s--) {
- a[k++] = value;
- }
- }
- } 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.
+ * Sorts the specified range of the array by counting sort.
*
* @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(short[] 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 void countingSort(short[] a, int left, int right) {
+ int[] count = new int[NUM_SHORT_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i] - Short.MIN_VALUE]++;
+ }
+ for (int i = NUM_SHORT_VALUES - 1, k = right; k >= left; i--) {
+ while (count[i] == 0) {
+ i--;
+ }
+ short value = (short) (i + Short.MIN_VALUE);
+ int s = count[i];
- // Sort these elements using a 5-element sorting network
- short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ do {
+ a[k--] = value;
+ } while (--s > 0);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
+ */
+ private static void sort(short[] a, int left, int right,boolean leftmost) {
+ int length = right - left + 1;
- if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ short ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ short ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
+
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
+
+ if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- short pivot1 = ae2; a[e2] = a[left];
- short pivot2 = ae4; a[e4] = a[right];
+ short pivot1 = a[e2];
+ short pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -767,16 +929,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
short ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -786,26 +946,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ short ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1;
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -813,20 +1054,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- short ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ short ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -834,92 +1074,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
a[k] = pivot1;
- a[great--] = ak;
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- short ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -928,7 +1109,11 @@
* @param a the array to be sorted
*/
public static void sort(char[] a) {
- doSort(a, 0, a.length - 1);
+ if (a.length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ countingSort(a, 0, a.length - 1);
+ } else {
+ sort(a, 0, a.length - 1, true);
+ }
}
/**
@@ -946,113 +1131,166 @@
*/
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- doSort(a, fromIndex, toIndex - 1);
+
+ if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ countingSort(a, fromIndex, toIndex - 1);
+ } else {
+ sort(a, fromIndex, toIndex - 1, true);
+ }
}
/** 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 i = left + 1; i <= right; i++) {
- char ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } 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.
+ * Sorts the specified range of the array by counting sort.
*
* @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;
+ private static void countingSort(char[] a, int left, int right) {
+ int[] count = new int[NUM_CHAR_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i]]++;
+ }
+ for (int i = 0, k = left; k <= right; i++) {
+ while (count[i] == 0) {
+ i++;
+ }
+ char value = (char) i;
+ int s = count[i];
- // Sort these elements using a 5-element sorting network
- char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ do {
+ a[k++] = value;
+ } while (--s > 0);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
+ */
+ private static void sort(char[] a, int left, int right, boolean leftmost) {
+ int length = right - left + 1;
- if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ char ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ char ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
+
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
+
+ if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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 = ae2; a[e2] = a[left];
- char pivot2 = ae4; a[e4] = a[right];
+ char pivot1 = a[e2];
+ char pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1060,16 +1298,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
char ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -1079,26 +1315,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ char ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1;
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1106,20 +1423,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- char ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ char ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -1127,92 +1443,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
a[k] = pivot1;
- a[great--] = ak;
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- char ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -1221,7 +1478,11 @@
* @param a the array to be sorted
*/
public static void sort(byte[] a) {
- doSort(a, 0, a.length - 1);
+ if (a.length > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+ countingSort(a, 0, a.length - 1);
+ } else {
+ sort(a, 0, a.length - 1, true);
+ }
}
/**
@@ -1239,115 +1500,166 @@
*/
public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- doSort(a, fromIndex, toIndex - 1);
+
+ if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+ countingSort(a, fromIndex, toIndex - 1);
+ } else {
+ sort(a, fromIndex, toIndex - 1, true);
+ }
}
/** 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. 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(byte[] a, int left, int right) {
- // Use insertion sort on tiny arrays
- if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
- for (int i = left + 1; i <= right; i++) {
- byte ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
- // Use counting sort on huge arrays
- int[] count = new int[NUM_BYTE_VALUES];
-
- for (int i = left; i <= right; i++) {
- count[a[i] - Byte.MIN_VALUE]++;
- }
- for (int i = 0, k = left; i < count.length && k <= right; i++) {
- byte value = (byte) (i + Byte.MIN_VALUE);
-
- for (int s = count[i]; s > 0; s--) {
- a[k++] = value;
- }
- }
- } 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.
+ * Sorts the specified range of the array by counting sort.
*
* @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(byte[] 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 void countingSort(byte[] a, int left, int right) {
+ int[] count = new int[NUM_BYTE_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i] - Byte.MIN_VALUE]++;
+ }
+ for (int i = NUM_BYTE_VALUES - 1, k = right; k >= left; i--) {
+ while (count[i] == 0) {
+ i--;
+ }
+ byte value = (byte) (i + Byte.MIN_VALUE);
+ int s = count[i];
- // Sort these elements using a 5-element sorting network
- byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ do {
+ a[k--] = value;
+ } while (--s > 0);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
+ */
+ private static void sort(byte[] a, int left, int right, boolean leftmost) {
+ int length = right - left + 1;
- if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ byte ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ byte ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
+
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { byte t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
+
+ if (a[e3] < a[e2]) { byte t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { byte t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { byte t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- byte pivot1 = ae2; a[e2] = a[left];
- byte pivot2 = ae4; a[e4] = a[right];
+ byte pivot1 = a[e2];
+ byte pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1355,16 +1667,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
byte ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -1374,26 +1684,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1;
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1401,20 +1792,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- byte ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ byte ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -1422,92 +1812,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
a[k] = pivot1;
- a[great--] = ak;
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- byte ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -1531,7 +1862,7 @@
* 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 and the call is a no-op).
+ * the range to be sorted is empty (and the call is a no-op).
*
* <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}
@@ -1565,162 +1896,207 @@
*/
private static void sortNegZeroAndNaN(float[] a, int left, int right) {
/*
- * Phase 1: Count negative zeros and move NaNs to end of array
+ * Phase 1: Move NaNs to the end of the array.
*/
- final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
- int numNegativeZeros = 0;
- int n = right;
-
- for (int k = left; k <= n; k++) {
+ while (left <= right && Float.isNaN(a[right])) {
+ right--;
+ }
+ for (int k = right - 1; k >= left; 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;
+ if (ak != ak) { // a[k] is NaN
+ a[k] = a[right];
+ a[right] = ak;
+ right--;
}
}
/*
- * Phase 2: Sort everything except NaNs (which are already in place)
+ * Phase 2: Sort everything except NaNs (which are already in place).
*/
- doSort(a, left, n);
+ sort(a, left, right, true);
/*
- * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ * Phase 3: Place negative zeros before positive zeros.
*/
- 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;
- }
+ int hi = right;
- // 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;
- }
- }
-
- /**
- * 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(float[] a, int low, int high) {
- while (true) {
- int middle = (low + high) >>> 1;
+ /*
+ * Search first zero, or first positive, or last negative element.
+ */
+ while (left < hi) {
+ int middle = (left + hi) >>> 1;
float middleValue = a[middle];
if (middleValue < 0.0f) {
- low = middle + 1;
- } else if (middleValue > 0.0f) {
- high = middle - 1;
- } else { // middleValue == 0.0f
- return middle;
+ left = middle + 1;
+ } else {
+ hi = middle;
+ }
+ }
+
+ /*
+ * Skip the last negative value (if any) or all leading negative zeros.
+ */
+ while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
+ left++;
+ }
+
+ /*
+ * Move negative zeros to the beginning of the sub-range.
+ *
+ * Partitioning:
+ *
+ * +---------------------------------------------------+
+ * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
+ * +---------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * left p k
+ *
+ * Invariants:
+ *
+ * all in (*, left) < 0.0
+ * all in [left, p) == -0.0
+ * all in [p, k) == 0.0
+ * all in [k, right] >= 0.0
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ for (int k = left + 1, p = left; k <= right; k++) {
+ float ak = a[k];
+ if (ak != 0.0f) {
+ break;
+ }
+ if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
+ a[k] = 0.0f;
+ a[p++] = -0.0f;
}
}
}
/**
- * 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.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
- */
- 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 i = left + 1; i <= right; i++) {
- float ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } 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.
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
*/
- private static void dualPivotQuicksort(float[] 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 void sort(float[] a, int left, int right,boolean leftmost) {
+ int length = right - left + 1;
- // Sort these elements using a 5-element sorting network
- float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ float ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ float ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
- if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
+
+ if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- float pivot1 = ae2; a[e2] = a[left];
- float pivot2 = ae4; a[e4] = a[right];
+ float pivot1 = a[e2];
+ float pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1728,16 +2104,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
float ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -1747,26 +2121,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ float ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = a[great];
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -1774,20 +2229,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- float ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ float ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -1795,92 +2249,33 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
- a[k] = pivot1;
- a[great--] = ak;
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
+ a[k] = a[great];
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- float ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
@@ -1938,162 +2333,207 @@
*/
private static void sortNegZeroAndNaN(double[] a, int left, int right) {
/*
- * Phase 1: Count negative zeros and move NaNs to end of array
+ * Phase 1: Move NaNs to the end of the array.
*/
- final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
- int numNegativeZeros = 0;
- int n = right;
-
- for (int k = left; k <= n; k++) {
+ while (left <= right && Double.isNaN(a[right])) {
+ right--;
+ }
+ for (int k = right - 1; k >= left; 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;
+ if (ak != ak) { // a[k] is NaN
+ a[k] = a[right];
+ a[right] = ak;
+ right--;
}
}
/*
- * Phase 2: Sort everything except NaNs (which are already in place)
+ * Phase 2: Sort everything except NaNs (which are already in place).
*/
- doSort(a, left, n);
+ sort(a, left, right, true);
/*
- * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ * Phase 3: Place negative zeros before positive zeros.
*/
- 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;
- }
+ int hi = right;
- // 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;
+ /*
+ * Search first zero, or first positive, or last negative element.
+ */
+ while (left < hi) {
+ int middle = (left + hi) >>> 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;
+ left = middle + 1;
+ } else {
+ hi = middle;
+ }
+ }
+
+ /*
+ * Skip the last negative value (if any) or all leading negative zeros.
+ */
+ while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
+ left++;
+ }
+
+ /*
+ * Move negative zeros to the beginning of the sub-range.
+ *
+ * Partitioning:
+ *
+ * +---------------------------------------------------+
+ * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
+ * +---------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * left p k
+ *
+ * Invariants:
+ *
+ * all in (*, left) < 0.0
+ * all in [left, p) == -0.0
+ * all in [p, k) == 0.0
+ * all in [k, right] >= 0.0
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ for (int k = left + 1, p = left; k <= right; k++) {
+ double ak = a[k];
+ if (ak != 0.0d) {
+ break;
+ }
+ if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
+ a[k] = 0.0d;
+ a[p++] = -0.0d;
}
}
}
/**
- * 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 i = left + 1; i <= right; i++) {
- double ai = a[i];
- int j;
- for (j = i - 1; j >= left && ai < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ai;
- }
- } 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.
+ * Dual-Pivot Quicksort algorithm. This method differs from the public
+ * {@code sort} method in that the {@code right} index is inclusive,
+ * it does no range checking on {@code left} or {@code right}, and has
+ * boolean flag whether insertion sort with sentinel is used or not.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
+ * @param leftmost indicates if the part is the most left in the range
*/
- private static void dualPivotQuicksort(double[] 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 void sort(double[] a, int left,int right,boolean leftmost) {
+ int length = right - left + 1;
- // Sort these elements using a 5-element sorting network
- double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD) {
+ if (!leftmost) {
+ /*
+ * Every element in adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid
+ * the j >= left check on each iteration.
+ */
+ for (int j, i = left + 1; i <= right; i++) {
+ double ai = a[i];
+ for (j = i - 1; ai < a[j]; j--) {
+ // assert j >= left;
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ai;
+ }
+ } else {
+ /*
+ * For case of leftmost part traditional (without a sentinel)
+ * insertion sort, optimized for server JVM, is used.
+ */
+ for (int i = left, j = i; i < right; j = ++i) {
+ double ai = a[i + 1];
+ while (ai < a[j]) {
+ a[j + 1] = a[j];
+ if (j-- == left) {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ return;
+ }
- if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
- if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
- if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
- if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
- if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
- if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
- if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
- if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
- if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
+ // Inexpensive approximation of length / 7
+ int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
- a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+ // Sort these elements using insertion sort
+ if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
+
+ if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+ }
+ }
+ if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+ if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+ if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+ if (t < a[e1]) { a[e2] = a[e1]; a[e1] = 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 elements to be sorted 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.
*/
- double pivot1 = ae2; a[e2] = a[left];
- double pivot2 = ae4; a[e4] = a[right];
+ double pivot1 = a[e2];
+ double pivot2 = a[e4];
// 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
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
- boolean pivotsDiffer = (pivot1 != pivot2);
+ if (pivot1 != pivot2) {
+ /*
+ * The first and the last elements to be sorted 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.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
- if (pivotsDiffer) {
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (a[++less] < pivot1);
+ while (a[--great] > pivot2);
+
/*
* Partitioning:
*
- * left part center part right part
- * +------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -2101,16 +2541,14 @@
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
outer:
for (int k = less; k <= great; k++) {
double ak = a[k];
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
} else if (ak > pivot2) { // Move a[k] to right part
while (a[great] > pivot2) {
@@ -2120,26 +2558,107 @@
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
- a[great--] = ak;
+ }
+ a[great] = ak;
+ great--;
+ }
+ }
+
+ // 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 pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 5/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great) {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ double ak = a[k];
+ if (ak == pivot1) { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ less++;
+ } else if (ak == pivot2) { // Move a[k] to right part
+ while (a[great] == pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = a[great];
+ less++;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ great--;
}
}
}
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
} else { // Pivots are equal
/*
- * Partition degenerates to the traditional 3-way,
- * or "Dutch National Flag", partition:
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
*
- * left part center part right part
- * +----------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +----------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
*
* Invariants:
*
@@ -2147,20 +2666,19 @@
* all in [less, k) == pivot
* all in (great, right) > pivot
*
- * Pointer k is the first index of ?-part
+ * Pointer k is the first index of ?-part.
*/
- for (int k = less; k <= great; k++) {
- double ak = a[k];
- if (ak == pivot1) {
+ for (int k = left; k <= great; k++) {
+ if (a[k] == pivot1) {
continue;
}
+ double ak = a[k];
+
if (ak < pivot1) { // Move a[k] to left part
- if (k != less) {
- a[k] = a[less];
- a[less] = ak;
- }
+ a[k] = a[less];
+ a[less] = ak;
less++;
- } else { // (a[k] > pivot1) - Move a[k] to right part
+ } else { // a[k] > pivot1 - Move a[k] to right part
/*
* We know that pivot1 == a[e3] == pivot2. Thus, we know
* that great will still be >= k when the following loop
@@ -2168,102 +2686,43 @@
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
+ // assert great > k;
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
- a[less++] = a[great];
- a[great--] = ak;
+ a[less] = a[great];
+ less++;
} else { // a[great] == pivot1
- a[k] = pivot1;
- a[great--] = ak;
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[k] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
+ a[k] = a[great];
}
+ a[great] = ak;
+ great--;
}
}
- }
-
- // 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 > 2/3 of the array),
- * swap internal pivot values to ends
- */
- if (less < e1 && great > e5) {
- while (a[less] == pivot1) {
- less++;
- }
- while (a[great] == pivot2) {
- great--;
- }
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part
- */
- outer:
- for (int k = less; k <= great; k++) {
- double ak = a[k];
- if (ak == pivot2) { // Move a[k] to right part
- while (a[great] == pivot2) {
- if (great-- == k) {
- break outer;
- }
- }
- if (a[great] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- } else { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great--] = pivot2;
- } else if (ak == pivot1) { // Move a[k] to left part
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
+ // Sort left and right parts recursively
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
}
-
- // Sort center part recursively, excluding known pivot values
- doSort(a, less, great);
}
/**
- * Checks that {@code fromIndex} and {@code toIndex} are in
- * the range and throws an appropriate exception, if they aren't.
+ * Checks that {@code fromIndex} and {@code toIndex} are in the range,
+ * otherwise throws an appropriate exception.
*/
private static void rangeCheck(int length, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
- "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ "fromIndex: " + fromIndex + " > toIndex: " + toIndex);
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
--- a/jdk/test/java/util/Arrays/Sorting.java Wed Jun 30 16:11:32 2010 -0700
+++ b/jdk/test/java/util/Arrays/Sorting.java Thu Jul 01 16:28:08 2010 +0100
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -43,10 +43,11 @@
// 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};
+ 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
// Array lengths used in a short run
- private static final int[] SHORT_RUN_LENGTHS = { 1, 2, 3, 21, 55, 1000, 10000 };
+ 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};
@@ -65,99 +66,338 @@
}
long end = System.currentTimeMillis();
- out.format("PASS in %d sec.\n", Math.round((end - start) / 1E3));
+ out.format("\nPASSED in %d sec.\n", Math.round((end - start) / 1E3));
}
private static void testAndCheck(int[] lengths, long[] randoms) {
+ testEmptyAndNullIntArray();
+ testEmptyAndNullLongArray();
+ testEmptyAndNullShortArray();
+ testEmptyAndNullCharArray();
+ testEmptyAndNullByteArray();
+ testEmptyAndNullFloatArray();
+ testEmptyAndNullDoubleArray();
+
for (long random : randoms) {
reset(random);
- for (int len : lengths) {
- testAndCheckWithCheckSum(len, random);
- }
- reset(random);
-
- for (int len : lengths) {
- testAndCheckWithScrambling(len, random);
+ for (int length : lengths) {
+ testAndCheckWithCheckSum(length, random);
}
reset(random);
- for (int len : lengths) {
- testAndCheckFloat(len, random);
+ for (int length : lengths) {
+ testAndCheckWithScrambling(length, random);
+ }
+ reset(random);
+
+ for (int length : lengths) {
+ testAndCheckFloat(length, random);
}
reset(random);
- for (int len : lengths) {
- testAndCheckDouble(len, random);
+ for (int length : lengths) {
+ testAndCheckDouble(length, random);
}
reset(random);
- for (int len : lengths) {
- testAndCheckRange(len, random);
+ for (int length : lengths) {
+ testAndCheckRange(length, random);
}
reset(random);
- for (int len : lengths) {
- testAndCheckSubArray(len, random);
+ for (int length : lengths) {
+ testAndCheckSubArray(length, random);
+ }
+ reset(random);
+
+ for (int length : lengths) {
+ testStable(length, random);
}
}
}
- private static void testAndCheckSubArray(int len, long random) {
- int[] golden = new int[len];
+ private static void testEmptyAndNullIntArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new int[] {});
+ Arrays.sort(new int[] {}, 0, 0);
+
+ try {
+ Arrays.sort((int[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((int[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(int[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullLongArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new long[] {});
+ Arrays.sort(new long[] {}, 0, 0);
+
+ try {
+ Arrays.sort((long[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((long[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(long[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullShortArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new short[] {});
+ Arrays.sort(new short[] {}, 0, 0);
+
+ try {
+ Arrays.sort((short[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((short[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(short[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullCharArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new char[] {});
+ Arrays.sort(new char[] {}, 0, 0);
- for (int m = 1; m < len / 2; m *= 2) {
+ try {
+ Arrays.sort((char[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((char[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(char[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullByteArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new byte[] {});
+ Arrays.sort(new byte[] {}, 0, 0);
+
+ try {
+ Arrays.sort((byte[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((byte[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(byte[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullFloatArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new float[] {});
+ Arrays.sort(new float[] {}, 0, 0);
+
+ try {
+ Arrays.sort((float[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((float[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(float[]) shouldn't catch null array");
+ }
+
+ private static void testEmptyAndNullDoubleArray() {
+ ourDescription = "Check empty and null array";
+ Arrays.sort(new double[] {});
+ Arrays.sort(new double[] {}, 0, 0);
+
+ try {
+ Arrays.sort((double[]) null);
+ } catch (NullPointerException expected) {
+ try {
+ Arrays.sort((double[]) null, 0, 0);
+ } catch (NullPointerException expected2) {
+ return;
+ }
+ failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " +
+ "catch null array");
+ }
+ failed("Arrays.sort(double[]) shouldn't catch null array");
+ }
+
+ private static void testAndCheckSubArray(int length, long random) {
+ ourDescription = "Check sorting of subarray";
+ int[] golden = new int[length];
+ boolean newLine = false;
+
+ for (int m = 1; m < length / 2; m *= 2) {
+ newLine = true;
int fromIndex = m;
- int toIndex = len - m;
+ int toIndex = length - m;
prepareSubArray(golden, fromIndex, toIndex, m);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
- out.println("Test #6: " + converter +
- " len = " + len + ", m = " + m);
+ out.println("Test 'subarray': " + converter +
+ " length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
-
- // outArr(test);
+ // outArray(test);
sortSubArray(convertedTest, fromIndex, toIndex);
- // outArr(test);
+ // outArray(test);
checkSubArray(convertedTest, fromIndex, toIndex, m);
}
}
+ if (newLine) {
+ out.println();
+ }
+ }
+
+ private static void testAndCheckRange(int length, long random) {
+ ourDescription = "Check range check";
+ int[] golden = new int[length];
+
+ for (int m = 1; m < 2 * length; m *= 2) {
+ for (int i = 1; i <= length; i++) {
+ golden[i - 1] = i % m + m % i;
+ }
+ for (TypeConverter converter : TypeConverter.values()) {
+ out.println("Test 'range': " + converter +
+ ", length = " + length + ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ checkRange(convertedGolden, m);
+ }
+ }
out.println();
}
- private static void testAndCheckRange(int len, long random) {
- int[] golden = new int[len];
+ private static void testStable(int length, long random) {
+ ourDescription = "Check if sorting is stable";
+ Pair[] a = build(length);
- for (int m = 1; m < 2 * len; m *= 2) {
- for (int i = 1; i <= len; i++) {
- golden[i - 1] = i % m + m % i;
+ out.println("Test 'stable': " + "random = " + random +
+ ", length = " + length);
+ Arrays.sort(a);
+ checkSorted(a);
+ checkStable(a);
+ }
+
+ private static void checkSorted(Pair[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i].getKey() > a[i + 1].getKey()) {
+ failed(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
}
- for (TypeConverter converter : TypeConverter.values()) {
- out.println("Test #5: " + converter +
- ", len = " + len + ", m = " + m);
- Object convertedGolden = converter.convert(golden);
- sortRange(convertedGolden, m);
- sortEmpty(convertedGolden);
+ }
+ }
+
+ private static void checkStable(Pair[] a) {
+ for (int i = 0; i < a.length / 4; ) {
+ int key1 = a[i].getKey();
+ int value1 = a[i++].getValue();
+ int key2 = a[i].getKey();
+ int value2 = a[i++].getValue();
+ int key3 = a[i].getKey();
+ int value3 = a[i++].getValue();
+ int key4 = a[i].getKey();
+ int value4 = a[i++].getValue();
+
+ if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
+ failed("On position " + i + " must keys are different " +
+ key1 + ", " + key2 + ", " + key3 + ", " + key4);
+ }
+ if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
+ failed("Sorting is not stable at position " + i +
+ ". Second values have been changed: " + value1 + ", " +
+ value2 + ", " + value3 + ", " + value4);
}
}
- out.println();
+ }
+
+ private static Pair[] build(int length) {
+ Pair[] a = new Pair[length * 4];
+
+ for (int i = 0; i < a.length; ) {
+ int key = ourRandom.nextInt();
+ a[i++] = new Pair(key, 1);
+ a[i++] = new Pair(key, 2);
+ a[i++] = new Pair(key, 3);
+ a[i++] = new Pair(key, 4);
+ }
+ return a;
}
- private static void testAndCheckWithCheckSum(int len, long random) {
- int[] golden = new int[len];
+ private static final class Pair implements Comparable<Pair> {
+ Pair(int key, int value) {
+ myKey = key;
+ myValue = value;
+ }
+
+ int getKey() {
+ return myKey;
+ }
+
+ int getValue() {
+ return myValue;
+ }
- for (int m = 1; m < 2 * len; m *= 2) {
+ public int compareTo(Pair pair) {
+ if (myKey < pair.myKey) {
+ return -1;
+ }
+ if (myKey > pair.myKey) {
+ return 1;
+ }
+ return 0;
+ }
+
+ @Override
+ public String toString() {
+ return "(" + myKey + ", " + myValue + ")";
+ }
+
+ private int myKey;
+ private int myValue;
+ }
+
+ private static void testAndCheckWithCheckSum(int length, long random) {
+ ourDescription = "Check sorting with check sum";
+ int[] golden = new int[length];
+
+ for (int m = 1; m < 2 * length; m *= 2) {
for (UnsortedBuilder builder : UnsortedBuilder.values()) {
builder.build(golden, m);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
- out.println("Test #1: " + converter + " " + builder +
- "random = " + random + ", len = " + len +
- ", m = " + m);
+ out.println("Test 'check sum': " + converter + " " +
+ builder + "random = " + random + ", length = " +
+ length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sort(convertedTest);
@@ -168,11 +408,12 @@
out.println();
}
- private static void testAndCheckWithScrambling(int len, long random) {
- int[] golden = new int[len];
+ private static void testAndCheckWithScrambling(int length, long random) {
+ ourDescription = "Check sorting with scrambling";
+ int[] golden = new int[length];
for (int m = 1; m <= 7; m++) {
- if (m > len) {
+ if (m > length) {
break;
}
for (SortedBuilder builder : SortedBuilder.values()) {
@@ -181,9 +422,9 @@
scramble(test);
for (TypeConverter converter : TypeConverter.values()) {
- out.println("Test #2: " + converter + " " + builder +
- "random = " + random + ", len = " + len +
- ", m = " + m);
+ out.println("Test 'scrambling': " + converter + " " +
+ builder + "random = " + random + ", length = " +
+ length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sort(convertedTest);
@@ -194,8 +435,9 @@
out.println();
}
- private static void testAndCheckFloat(int len, long random) {
- float[] golden = new float[len];
+ private static void testAndCheckFloat(int length, long random) {
+ ourDescription = "Check float sorting";
+ float[] golden = new float[length];
final int MAX = 10;
boolean newLine = false;
@@ -204,22 +446,23 @@
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) {
+ if (a + g + z + n + p > length) {
continue;
}
- if (a + g + z + n + p < len) {
+ if (a + g + z + n + p < length) {
continue;
}
for (FloatBuilder builder : FloatBuilder.values()) {
- out.println("Test #3: random = " + random +
- ", len = " + len + ", a = " + a + ", g = " + g +
- ", z = " + z + ", n = " + n + ", p = " + p);
+ out.println("Test 'float': random = " + random +
+ ", length = " + length + ", 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);
+ // outArray(test);
sort(test);
- // outArr(test);
+ // outArray(test);
compare(test, golden, a, n, g);
}
newLine = true;
@@ -233,8 +476,9 @@
}
}
- private static void testAndCheckDouble(int len, long random) {
- double[] golden = new double[len];
+ private static void testAndCheckDouble(int length, long random) {
+ ourDescription = "Check double sorting";
+ double[] golden = new double[length];
final int MAX = 10;
boolean newLine = false;
@@ -243,22 +487,22 @@
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) {
+ if (a + g + z + n + p > length) {
continue;
}
- if (a + g + z + n + p < len) {
+ if (a + g + z + n + p < length) {
continue;
}
for (DoubleBuilder builder : DoubleBuilder.values()) {
- out.println("Test #4: random = " + random +
- ", len = " + len + ", a = " + a + ", g = " + g +
- ", z = " + z + ", n = " + n + ", p = " + p);
+ out.println("Test 'double': random = " + random +
+ ", length = " + length + ", 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);
+ // outArray(test);
sort(test);
- // outArr(test);
+ // outArray(test);
compare(test, golden, a, n, g);
}
newLine = true;
@@ -276,37 +520,29 @@
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));
+ for (int i = 0; i < a.length * 7; i++) {
+ swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.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));
+ for (int i = 0; i < a.length * 7; i++) {
+ swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.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));
+ for (int i = 0; i < a.length * 7; i++) {
+ swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
}
}
@@ -393,6 +629,16 @@
}
return b;
}
+ },
+ INTEGER {
+ Object convert(int[] a) {
+ Integer[] b = new Integer[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = new Integer(a[i]);
+ }
+ return b;
+ }
};
abstract Object convert(int[] a);
@@ -691,6 +937,8 @@
compare((float[]) test, (float[]) golden);
} else if (test instanceof double[]) {
compare((double[]) test, (double[]) golden);
+ } else if (test instanceof Integer[]) {
+ compare((Integer[]) test, (Integer[]) golden);
} else {
failed("Unknow type of array: " + test + " of class " +
test.getClass().getName());
@@ -703,13 +951,13 @@
}
private static void failed(String message) {
- err.format("\n*** FAILED: %s\n\n", message);
+ err.format("\n*** TEST FAILED - %s\n\n%s\n\n", ourDescription, message);
throw new RuntimeException("Test failed - see log file for details");
}
private static void failed(int index, String value1, String value2) {
- failed("Array is not sorted at " + index + "-th position: " + value1 +
- " and " + value2);
+ failed("Array is not sorted at " + index + "-th position: " +
+ value1 + " and " + value2);
}
private static void checkSorted(Object object) {
@@ -727,12 +975,22 @@
checkSorted((float[]) object);
} else if (object instanceof double[]) {
checkSorted((double[]) object);
+ } else if (object instanceof Integer[]) {
+ checkSorted((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
+ private static void compare(Integer[] a, Integer[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i].intValue() != b[i].intValue()) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
private static void compare(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
@@ -789,6 +1047,14 @@
}
}
+ private static void checkSorted(Integer[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i].intValue() > a[i + 1].intValue()) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
private static void checkSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
@@ -847,7 +1113,7 @@
private static void checkCheckSum(Object test, Object golden) {
if (checkSum(test) != checkSum(golden)) {
- failed("Original and sorted arrays seems not identical");
+ failed("It seems that original and sorted arrays are not identical");
}
}
@@ -866,6 +1132,8 @@
return checkSum((float[]) object);
} else if (object instanceof double[]) {
return checkSum((double[]) object);
+ } else if (object instanceof Integer[]) {
+ return checkSum((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
@@ -873,6 +1141,15 @@
}
}
+ private static int checkSum(Integer[] a) {
+ int checkXorSum = 0;
+
+ for (Integer e : a) {
+ checkXorSum ^= e.intValue();
+ }
+ return checkXorSum;
+ }
+
private static int checkSum(int[] a) {
int checkXorSum = 0;
@@ -951,6 +1228,8 @@
Arrays.sort((float[]) object);
} else if (object instanceof double[]) {
Arrays.sort((double[]) object);
+ } else if (object instanceof Integer[]) {
+ Arrays.sort((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
@@ -972,6 +1251,8 @@
Arrays.sort((float[]) object, fromIndex, toIndex);
} else if (object instanceof double[]) {
Arrays.sort((double[]) object, fromIndex, toIndex);
+ } else if (object instanceof Integer[]) {
+ Arrays.sort((Integer[]) object, fromIndex, toIndex);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
@@ -993,12 +1274,36 @@
checkSubArray((float[]) object, fromIndex, toIndex, m);
} else if (object instanceof double[]) {
checkSubArray((double[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof Integer[]) {
+ checkSubArray((Integer[]) object, fromIndex, toIndex, m);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
+ private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i].intValue() != 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].intValue() > a[i + 1].intValue()) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i].intValue() != 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != 0xBABA) {
@@ -1153,49 +1458,30 @@
}
}
- private static void sortRange(Object object, int m) {
+ private static void checkRange(Object object, int m) {
if (object instanceof int[]) {
- sortRange((int[]) object, m);
+ checkRange((int[]) object, m);
} else if (object instanceof long[]) {
- sortRange((long[]) object, m);
+ checkRange((long[]) object, m);
} else if (object instanceof short[]) {
- sortRange((short[]) object, m);
+ checkRange((short[]) object, m);
} else if (object instanceof byte[]) {
- sortRange((byte[]) object, m);
+ checkRange((byte[]) object, m);
} else if (object instanceof char[]) {
- sortRange((char[]) object, m);
+ checkRange((char[]) object, m);
} else if (object instanceof float[]) {
- sortRange((float[]) object, m);
+ checkRange((float[]) object, m);
} else if (object instanceof double[]) {
- sortRange((double[]) object, m);
+ checkRange((double[]) object, m);
+ } else if (object instanceof Integer[]) {
+ checkRange((Integer[]) object, m);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
- private static void 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) {
+ private static void checkRange(Integer[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1224,7 +1510,36 @@
}
}
- private static void sortRange(long[] a, int m) {
+ private static void checkRange(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 checkRange(long[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1253,7 +1568,7 @@
}
}
- private static void sortRange(byte[] a, int m) {
+ private static void checkRange(byte[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1282,7 +1597,7 @@
}
}
- private static void sortRange(short[] a, int m) {
+ private static void checkRange(short[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1311,7 +1626,7 @@
}
}
- private static void sortRange(char[] a, int m) {
+ private static void checkRange(char[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1340,7 +1655,7 @@
}
}
- private static void sortRange(float[] a, int m) {
+ private static void checkRange(float[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1369,7 +1684,7 @@
}
}
- private static void sortRange(double[] a, int m) {
+ private static void checkRange(double[] a, int m) {
try {
Arrays.sort(a, m + 1, m);
@@ -1410,31 +1725,36 @@
ourSecond = 0;
}
- private static void outArr(int[] a) {
+ private static void outArray(Object[] a) {
+ for (int i = 0; i < a.length; i++) {
+ out.print(a[i] + " ");
+ }
+ out.println();
+ }
+
+ private static void outArray(int[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
- out.println();
}
- private static void outArr(float[] a) {
+ private static void outArray(float[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
- out.println();
}
- private static void outArr(double[] a) {
+ private static void outArray(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;
+ private static String ourDescription;
}