Back to index...

	/*
	* Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package java.util;

	/**
	* 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.
	*
	* All exposed methods are package-private, designed to be invoked
	* from public methods (in class Arrays) after performing any
	* necessary array bounds checks and expanding parameters into the
	* required forms.
	*
	* @author Vladimir Yaroslavskiy
	* @author Jon Bentley
	* @author Josh Bloch
	*
	* @version 2011.02.11 m765.827.12i:5\7pm
	* @since 1.7
	*/
	final class DualPivotQuicksort {

	/**
	* Prevents instantiation.
	*/
	private DualPivotQuicksort() {}

	/*
	* Tuning parameters.
	*/

	/**
	* The maximum number of runs in merge sort.
	*/
	private static final int MAX_RUN_COUNT = 67;

	/**
	* The maximum length of run in merge sort.
	*/
	private static final int MAX_RUN_LENGTH = 33;

	/**
	* If the length of an array to be sorted is less than this
	* constant, Quicksort is used in preference to merge sort.
	*/
	private static final int QUICKSORT_THRESHOLD = 286;

	/**
	* 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 = 47;

	/**
	* If the length of a byte array to be sorted is greater than this
	* constant, counting sort is used in preference to insertion sort.
	*/
	private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

	/**
	* 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 = 3200;

	/*
	* Sorting methods for seven primitive types.
	*/

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(int[] a, int left, int right,
	int[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	int[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new int[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	int[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(int[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	int a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	int last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

	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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	int ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	int pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	int ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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] = pivot;
	}
	a[great] = ak;
	--great;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(long[] a, int left, int right,
	long[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	long[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new long[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	long[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(long[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	long a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	long last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

	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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	long ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	long pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	long ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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] = pivot;
	}
	a[great] = ak;
	--great;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(short[] a, int left, int right,
	short[] work, int workBase, int workLen) {
	// Use counting sort on large arrays
	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
	int[] count = new int[NUM_SHORT_VALUES];

	for (int i = left - 1; ++i <= right;
	count[a[i] - Short.MIN_VALUE]++
	);
	for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
	while (count[--i] == 0);
	short value = (short) (i + Short.MIN_VALUE);
	int s = count[i];

	do {
	a[--k] = value;
	} while (--s > 0);
	}
	} else { // Use Dual-Pivot Quicksort on small arrays
	doSort(a, left, right, work, workBase, workLen);
	}
	}

	/** The number of distinct short values. */
	private static final int NUM_SHORT_VALUES = 1 << 16;

	/**
	* Sorts the specified range of the array.
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	private static void doSort(short[] a, int left, int right,
	short[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	short[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new short[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	short[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(short[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	short a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	short last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	short ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	short pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	short ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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] = pivot;
	}
	a[great] = ak;
	--great;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(char[] a, int left, int right,
	char[] work, int workBase, int workLen) {
	// Use counting sort on large arrays
	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
	int[] count = new int[NUM_CHAR_VALUES];

	for (int i = left - 1; ++i <= right;
	count[a[i]]++
	);
	for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
	while (count[--i] == 0);
	char value = (char) i;
	int s = count[i];

	do {
	a[--k] = value;
	} while (--s > 0);
	}
	} else { // Use Dual-Pivot Quicksort on small arrays
	doSort(a, left, right, work, workBase, workLen);
	}
	}

	/** The number of distinct char values. */
	private static final int NUM_CHAR_VALUES = 1 << 16;

	/**
	* Sorts the specified range of the array.
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	private static void doSort(char[] a, int left, int right,
	char[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	char[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new char[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	char[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(char[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	char a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	char last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	char ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	char pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	char ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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] = pivot;
	}
	a[great] = ak;
	--great;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}

	/** The number of distinct byte values. */
	private static final int NUM_BYTE_VALUES = 1 << 8;

	/**
	* Sorts the specified range of the array.
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	*/
	static void sort(byte[] a, int left, int right) {
	// Use counting sort on large arrays
	if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
	int[] count = new int[NUM_BYTE_VALUES];

	for (int i = left - 1; ++i <= right;
	count[a[i] - Byte.MIN_VALUE]++
	);
	for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
	while (count[--i] == 0);
	byte value = (byte) (i + Byte.MIN_VALUE);
	int s = count[i];

	do {
	a[--k] = value;
	} while (--s > 0);
	}
	} else { // Use insertion sort on small arrays
	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;
	}
	}
	}

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(float[] a, int left, int right,
	float[] work, int workBase, int workLen) {
	/*
	* Phase 1: Move NaNs to the end of the array.
	*/
	while (left <= right && Float.isNaN(a[right])) {
	--right;
	}
	for (int k = right; --k >= left; ) {
	float ak = a[k];
	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).
	*/
	doSort(a, left, right, work, workBase, workLen);

	/*
	* Phase 3: Place negative zeros before positive zeros.
	*/
	int hi = right;

	/*
	* Find the 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) {
	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, p = left - 1; ++k <= right; ) {
	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.
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	private static void doSort(float[] a, int left, int right,
	float[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	float[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new float[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	float[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(float[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	float a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	float last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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]) { 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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	float ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	float pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	float ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}

	/**
	* Sorts the specified range of the array using the given
	* workspace array slice if possible for merging
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	static void sort(double[] a, int left, int right,
	double[] work, int workBase, int workLen) {
	/*
	* Phase 1: Move NaNs to the end of the array.
	*/
	while (left <= right && Double.isNaN(a[right])) {
	--right;
	}
	for (int k = right; --k >= left; ) {
	double ak = a[k];
	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).
	*/
	doSort(a, left, right, work, workBase, workLen);

	/*
	* Phase 3: Place negative zeros before positive zeros.
	*/
	int hi = right;

	/*
	* Find the 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) {
	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, p = left - 1; ++k <= right; ) {
	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.
	*
	* @param a the array to be sorted
	* @param left the index of the first element, inclusive, to be sorted
	* @param right the index of the last element, inclusive, to be sorted
	* @param work a workspace array (slice)
	* @param workBase origin of usable space in work array
	* @param workLen usable size of work array
	*/
	private static void doSort(double[] a, int left, int right,
	double[] work, int workBase, int workLen) {
	// Use Quicksort on small arrays
	if (right - left < QUICKSORT_THRESHOLD) {
	sort(a, left, right, true);
	return;
	}

	/*
	* Index run[i] is the start of i-th run
	* (ascending or descending sequence).
	*/
	int[] run = new int[MAX_RUN_COUNT + 1];
	int count = 0; run[0] = left;

	// Check if the array is nearly sorted
	for (int k = left; k < right; run[count] = k) {
	if (a[k] < a[k + 1]) { // ascending
	while (++k <= right && a[k - 1] <= a[k]);
	} else if (a[k] > a[k + 1]) { // descending
	while (++k <= right && a[k - 1] >= a[k]);
	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
	double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
	}
	} else { // equal
	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
	if (--m == 0) {
	sort(a, left, right, true);
	return;
	}
	}
	}

	/*
	* The array is not highly structured,
	* use Quicksort instead of merge sort.
	*/
	if (++count == MAX_RUN_COUNT) {
	sort(a, left, right, true);
	return;
	}
	}

	// Check special cases
	// Implementation note: variable "right" is increased by 1.
	if (run[count] == right++) { // The last run contains one element
	run[++count] = right;
	} else if (count == 1) { // The array is already sorted
	return;
	}

	// Determine alternation base for merge
	byte odd = 0;
	for (int n = 1; (n <<= 1) < count; odd ^= 1);

	// Use or create temporary array b for merging
	double[] b; // temp array; alternates with a
	int ao, bo; // array offsets from 'left'
	int blen = right - left; // space needed for b
	if (work == null \|\| workLen < blen \|\| workBase + blen > work.length) {
	work = new double[blen];
	workBase = 0;
	}
	if (odd == 0) {
	System.arraycopy(a, left, work, workBase, blen);
	b = a;
	bo = 0;
	a = work;
	ao = workBase - left;
	} else {
	b = work;
	ao = 0;
	bo = workBase - left;
	}

	// Merging
	for (int last; count > 1; count = last) {
	for (int k = (last = 0) + 2; k <= count; k += 2) {
	int hi = run[k], mi = run[k - 1];
	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
	if (q >= hi \|\| p < mi && a[p + ao] <= a[q + ao]) {
	b[i + bo] = a[p++ + ao];
	} else {
	b[i + bo] = a[q++ + ao];
	}
	}
	run[++last] = hi;
	}
	if ((count & 1) != 0) {
	for (int i = right, lo = run[count - 1]; --i >= lo;
	b[i + bo] = a[i + ao]
	);
	run[++last] = right;
	}
	double[] t = a; a = b; b = t;
	int o = ao; ao = bo; bo = o;
	}
	}

	/**
	* Sorts the specified range of the array by Dual-Pivot Quicksort.
	*
	* @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 this part is the leftmost in the range
	*/
	private static void sort(double[] a, int left, int right, boolean leftmost) {
	int length = right - left + 1;

	// Use insertion sort on tiny arrays
	if (length < INSERTION_SORT_THRESHOLD) {
	if (leftmost) {
	/*
	* Traditional (without sentinel) insertion sort,
	* optimized for server VM, is used in case of
	* the leftmost part.
	*/
	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;
	}
	} else {
	/*
	* Skip the longest ascending sequence.
	*/
	do {
	if (left >= right) {
	return;
	}
	} while (a[++left] >= a[left - 1]);

	/*
	* Every element from adjoining part plays the role
	* of sentinel, therefore this allows us to avoid the
	* left range check on each iteration. Moreover, we use
	* the more optimized algorithm, so called pair insertion
	* sort, which is faster (in the context of Quicksort)
	* than traditional implementation of insertion sort.
	*/
	for (int k = left; ++left <= right; k = ++left) {
	double a1 = a[k], a2 = a[left];

	if (a1 < a2) {
	a2 = a1; a1 = a[left];
	}
	while (a1 < a[--k]) {
	a[k + 2] = a[k];
	}
	a[++k + 1] = a1;

	while (a2 < a[--k]) {
	a[k + 1] = a[k];
	}
	a[k + 1] = a2;
	}
	double last = a[right];

	while (last < a[--right]) {
	a[right + 1] = a[right];
	}
	a[right + 1] = last;
	}
	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 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]) { 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; }
	}
	}
	}

	// 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 (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
	/*
	* 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];

	/*
	* 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];

	/*
	* 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
	*
	* Invariants:
	*
	* all in (left, less) < pivot1
	* pivot1 <= all in [less, k) <= pivot2
	* all in (great, right) > pivot2
	*
	* Pointer k is the first index of ?-part.
	*/
	outer:
	for (int k = less - 1; ++k <= great; ) {
	double ak = a[k];
	if (ak < pivot1) { // Move a[k] to left part
	a[k] = a[less];
	/*
	* Here and below we use "a[i] = b; i++;" instead
	* of "a[i++] = b;" due to performance issue.
	*/
	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[great] <= pivot2
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // pivot1 <= a[great] <= pivot2
	a[k] = a[great];
	}
	/*
	* Here and below we use "a[i] = b; i--;" instead
	* of "a[i--] = b;" due to performance issue.
	*/
	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 > 4/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 - 1; ++k <= great; ) {
	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[great] < pivot2
	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 { // Partitioning with one pivot
	/*
	* Use the third of the five sorted elements as pivot.
	* This value is inexpensive approximation of the median.
	*/
	double pivot = a[e3];

	/*
	* Partitioning 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 ?-part.
	*/
	for (int k = less; k <= great; ++k) {
	if (a[k] == pivot) {
	continue;
	}
	double ak = a[k];
	if (ak < pivot) { // Move a[k] to left part
	a[k] = a[less];
	a[less] = ak;
	++less;
	} else { // a[k] > pivot - Move a[k] to right part
	while (a[great] > pivot) {
	--great;
	}
	if (a[great] < pivot) { // a[great] <= pivot
	a[k] = a[less];
	a[less] = a[great];
	++less;
	} else { // a[great] == pivot
	/*
	* Even though a[great] equals to pivot, the
	* assignment a[k] = pivot may be incorrect,
	* if a[great] and pivot 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;
	}
	}

	/*
	* Sort left and right parts recursively.
	* All elements from center part are equal
	* and, therefore, already sorted.
	*/
	sort(a, left, less - 1, leftmost);
	sort(a, great + 1, right, false);
	}
	}
	}

Back to index...