/*
* Copyright 2010 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Sun designates this
* particular file as subject to the "Classpath" exception as provided
* by Sun in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.com if you need additional information or
* have any questions.
*/
package java.util;
/**
* This class implements the Dual-Pivot Quicksort algorithm by
* 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.
*
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
*
* @version 2010.04.25 m765.827.12i:5\7
* @since 1.7
*/
final class DualPivotQuicksort {
/**
* Prevents instantiation.
*/
private DualPivotQuicksort() {}
/*
* Tuning parameters.
*/
/**
* If the length of an array to be sorted is less than this
* constant, insertion sort is used in preference to Quicksort.
*/
private static final int INSERTION_SORT_THRESHOLD = 32;
/**
* If the length of a byte array to be sorted is greater than
* this constant, counting sort is used in preference to Quicksort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
/**
* If the length of a short or char array to be sorted is greater
* than this constant, counting sort is used in preference to Quicksort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
/*
* Sorting methods for seven primitive types.
*/
/**
* Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
dualPivotQuicksort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, fromIndex, toIndex - 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) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set minimum value as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
int before = a[left - 1]; a[left - 1] = Integer.MIN_VALUE;
for (int j, i = left + 1; i <= right; i++) {
int ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
int ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
int pivot1 = a[e2];
int pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
int ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
*/
public static void sort(long[] a) {
dualPivotQuicksort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, fromIndex, toIndex - 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) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set minimum value as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
long before = a[left - 1]; a[left - 1] = Long.MIN_VALUE;
for (int j, i = left + 1; i <= right; i++) {
long ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
long ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
long ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
long pivot1 = a[e2];
long pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
long ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
*/
public static void sort(short[] a) {
dualPivotQuicksort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, fromIndex, toIndex - 1);
}
/** The number of distinct short values. */
private static final int NUM_SHORT_VALUES = 1 << 16;
/**
* Sorts the specified range of the array into ascending order 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(short[] a, int left, int right) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set minimum value as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
short before = a[left - 1]; a[left - 1] = Short.MIN_VALUE;
for (int j, i = left + 1; i <= right; i++) {
short ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
short ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Use counting sort on huge arrays
if (length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
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;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
short ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; }
a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
short pivot1 = a[e2];
short pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
short ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
*/
public static void sort(char[] a) {
dualPivotQuicksort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, fromIndex, toIndex - 1);
}
/** The number of distinct char values. */
private static final int NUM_CHAR_VALUES = 1 << 16;
/**
* Sorts the specified range of the array into ascending order by the
* Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(char[] a, int left, int right) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set minimum value as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
char before = a[left - 1]; a[left - 1] = Character.MIN_VALUE;
for (int j, i = left + 1; i <= right; i++) {
char ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
char ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Use counting sort on huge arrays
if (length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
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;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
char ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; }
a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
char pivot1 = a[e2];
char pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
char ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
*/
public static void sort(byte[] a) {
dualPivotQuicksort(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, fromIndex, toIndex - 1);
}
/** The number of distinct byte values. */
private static final int NUM_BYTE_VALUES = 1 << 8;
/**
* Sorts the specified range of the array into ascending order 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(byte[] a, int left, int right) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set minimum value as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
byte before = a[left - 1]; a[left - 1] = Byte.MIN_VALUE;
for (int j, i = left + 1; i <= right; i++) {
byte ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
byte ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Use counting sort on huge arrays
if (length > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
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;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
byte ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; }
a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
byte pivot1 = a[e2];
byte pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
byte ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
* The {@code <} relation does not provide a total order on all float
* values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
* value compares neither less than, greater than, nor equal to any value,
* even itself. This method uses the total order imposed by the method
* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
* {@code 0.0f} and {@code Float.NaN} is considered greater than any
* other value and all {@code Float.NaN} values are considered equal.
*
* @param a the array to be sorted
*/
public static void sort(float[] a) {
sortNegZeroAndNaN(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. 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 {@code <} relation does not provide a total order on all float
* values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
* value compares neither less than, greater than, nor equal to any value,
* even itself. This method uses the total order imposed by the method
* {@link Float#compareTo}: {@code -0.0f} is treated as less than value
* {@code 0.0f} and {@code Float.NaN} is considered greater than any
* other value and all {@code Float.NaN} values are considered equal.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
}
/**
* Sorts the specified range of the array into ascending order. The
* sort is done in three phases to avoid expensive comparisons in the
* inner loop. The comparisons would be expensive due to anomalies
* associated with negative zero {@code -0.0f} and {@code Float.NaN}.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
*/
private static void sortNegZeroAndNaN(float[] a, int left, int right) {
/*
* Phase 1: Count negative zeros and move NaNs to end of array.
*/
final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
int numNegativeZeros = 0;
int n = right;
for (int k = left; k <= n; k++) {
float ak = a[k];
if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
a[k] = 0.0f;
numNegativeZeros++;
} else if (ak != ak) { // i.e., ak is NaN
a[k--] = a[n];
a[n--] = Float.NaN;
}
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
dualPivotQuicksort(a, left, n);
/*
* Phase 3: Turn positive zeros back into negative 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;
}
// 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;
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;
}
}
}
/**
* 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(float[] a, int left, int right) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set negative infinity as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
float before = a[left-1]; a[left-1] = Float.NEGATIVE_INFINITY;
for (int j, i = left + 1; i <= right; i++) {
float ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
float ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
float ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; }
a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
float pivot1 = a[e2];
float pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
float ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Sorts the specified array into ascending numerical order.
*
*
The {@code <} relation does not provide a total order on all double
* values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
* value compares neither less than, greater than, nor equal to any value,
* even itself. This method uses the total order imposed by the method
* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
* {@code 0.0d} and {@code Double.NaN} is considered greater than any
* other value and all {@code Double.NaN} values are considered equal.
*
* @param a the array to be sorted
*/
public static void sort(double[] a) {
sortNegZeroAndNaN(a, 0, a.length - 1);
}
/**
* Sorts the specified range of the array into ascending order. The range
* to be sorted extends from the index {@code fromIndex}, inclusive, to
* the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty (and the call is a no-op).
*
*
The {@code <} relation does not provide a total order on all double
* values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
* value compares neither less than, greater than, nor equal to any value,
* even itself. This method uses the total order imposed by the method
* {@link Double#compareTo}: {@code -0.0d} is treated as less than value
* {@code 0.0d} and {@code Double.NaN} is considered greater than any
* other value and all {@code Double.NaN} values are considered equal.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element, inclusive, to be sorted
* @param toIndex the index of the last element, exclusive, to be sorted
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
}
/**
* Sorts the specified range of the array into ascending order. The
* sort is done in three phases to avoid expensive comparisons in the
* inner loop. The comparisons would be expensive due to anomalies
* associated with negative zero {@code -0.0d} and {@code Double.NaN}.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
*/
private static void sortNegZeroAndNaN(double[] a, int left, int right) {
/*
* Phase 1: Count negative zeros and move NaNs to end of array.
*/
final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
int numNegativeZeros = 0;
int n = right;
for (int k = left; k <= n; k++) {
double ak = a[k];
if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
a[k] = 0.0d;
numNegativeZeros++;
} else if (ak != ak) { // i.e., ak is NaN
a[k--] = a[n];
a[n--] = Double.NaN;
}
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
dualPivotQuicksort(a, left, n);
/*
* Phase 3: Turn positive zeros back into negative 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;
}
// Turn the right number of positive zeros back into negative zeros
for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
a[i] = -0.0d;
}
}
/**
* Returns the index of some zero element in the specified range via
* binary search. The range is assumed to be sorted, and must contain
* at least one zero.
*
* @param a the array to be searched
* @param low the index of the first element, inclusive, to be searched
* @param high the index of the last element, inclusive, to be searched
*/
private static int findAnyZero(double[] a, int low, int high) {
while (true) {
int middle = (low + high) >>> 1;
double middleValue = a[middle];
if (middleValue < 0.0d) {
low = middle + 1;
} else if (middleValue > 0.0d) {
high = middle - 1;
} else { // middleValue == 0.0d
return middle;
}
}
}
/**
* Sorts the specified range of the array into ascending order 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(double[] a, int left, int right) {
int length = right - left + 1;
// Skip trivial arrays
if (length < 2) {
return;
}
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (left > 0) {
/*
* Set negative infinity as a sentinel before the specified
* range of the array, it allows to avoid expensive
* check j >= left on each iteration.
*/
double before = a[left-1];a[left-1] = Double.NEGATIVE_INFINITY;
for (int j, i = left + 1; i <= right; i++) {
double ai = a[i];
for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
a[left - 1] = before;
} else {
/*
* For case, when left == 0, traditional (without a sentinel)
* insertion sort, optimized for server VM, is used.
*/
for (int i = 0, j = i; i < right; j = ++i) {
double ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == 0) {
break;
}
}
a[j + 1] = ai;
}
}
return;
}
// Inexpensive approximation of one seventh
int seventh = (length >>> 3) + (length >>> 6) + 1;
// Compute indices of 5 center evenly spaced elements
int e3 = (left + right) >>> 1; // The midpoint
int e2 = e3 - seventh, e1 = e2 - seventh;
int e4 = e3 + seventh, e5 = e4 + seventh;
// Sort these elements using a 5-element sorting network
double ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
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; }
a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
/*
* 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.
*/
double pivot1 = a[e2];
double pivot2 = a[e4];
// Pointers
int less = left; // The index of the first element of center part
int great = right; // The index before the first element of right part
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[less++];
a[e4] = a[great--];
/*
* Partitioning:
*
* left part center part right part
* +--------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +--------------------------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot1
* pivot1 <= all in [less, k) <= pivot2
* all in (great, right) > pivot2
*
* Pointer k is the first index of not inspected ?-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;
}
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];
a[less++] = a[great];
} else { // pivot1 <= a[great] <= pivot2
a[k] = a[great];
}
a[great--] = ak;
}
}
// Swap pivots into their final positions
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivots
dualPivotQuicksort(a, left, less - 2);
dualPivotQuicksort(a, great + 2, right);
/*
* If center part is too large (comprises > 5/7 of the array),
* swap internal pivot values to ends.
*/
if (great - less > 5 * seventh) {
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 not inspected ?-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 center part recursively
dualPivotQuicksort(a, less, great);
} else { // Pivots are equal
/*
* Partition degenerates to the traditional 3-way
* (or "Dutch National Flag") schema:
*
* left part center part right part
* +----------------------------------------------+
* | < pivot | == pivot | ? | > pivot |
* +----------------------------------------------+
* ^ ^ ^
* | | |
* less k great
*
* Invariants:
*
* all in (left, less) < pivot
* all in [less, k) == pivot
* all in (great, right) > pivot
*
* Pointer k is the first index of not inspected ?-part.
*/
for (int k = less; k <= great; k++) {
double ak = a[k];
if (ak == pivot1) {
continue;
}
if (ak < pivot1) { // Move a[k] to left part
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} 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
* terminates, even though we don't test for it explicitly.
* In other words, a[e3] acts as a sentinel for great.
*/
while (a[great] > pivot1) {
great--;
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less++] = a[great];
} else { // a[great] == pivot1
a[k] = pivot1;
}
a[great--] = ak;
}
}
// Sort left and right parts recursively
dualPivotQuicksort(a, left, less - 1);
dualPivotQuicksort(a, great + 1, right);
}
}
/**
* Checks that {@code fromIndex} and {@code toIndex} are in
* the range and throws an appropriate exception, if they aren't.
*/
private static void rangeCheck(int length, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex: " + fromIndex + " > toIndex: " + toIndex);
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > length) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
}