hg/bck2brwsr: rt/emul/compact/src/main/java/java/util/DualPivotQuicksort.java@d382dacfd73f (annotated)

jaroslav@559	1	/*
jaroslav@559	2	* Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
jaroslav@559	3	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@559	4	*
jaroslav@559	5	* This code is free software; you can redistribute it and/or modify it
jaroslav@559	6	* under the terms of the GNU General Public License version 2 only, as
jaroslav@559	7	* published by the Free Software Foundation. Oracle designates this
jaroslav@559	8	* particular file as subject to the "Classpath" exception as provided
jaroslav@559	9	* by Oracle in the LICENSE file that accompanied this code.
jaroslav@559	10	*
jaroslav@559	11	* This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@559	12	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@559	13	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
jaroslav@559	14	* version 2 for more details (a copy is included in the LICENSE file that
jaroslav@559	15	* accompanied this code).
jaroslav@559	16	*
jaroslav@559	17	* You should have received a copy of the GNU General Public License version
jaroslav@559	18	* 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@559	19	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@559	20	*
jaroslav@559	21	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@559	22	* or visit www.oracle.com if you need additional information or have any
jaroslav@559	23	* questions.
jaroslav@559	24	*/
jaroslav@559	25
jaroslav@559	26	package java.util;
jaroslav@559	27
jaroslav@559	28	/**
jaroslav@559	29	* This class implements the Dual-Pivot Quicksort algorithm by
jaroslav@559	30	* Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
jaroslav@559	31	* offers O(n log(n)) performance on many data sets that cause other
jaroslav@559	32	* quicksorts to degrade to quadratic performance, and is typically
jaroslav@559	33	* faster than traditional (one-pivot) Quicksort implementations.
jaroslav@559	34	*
jaroslav@559	35	* @author Vladimir Yaroslavskiy
jaroslav@559	36	* @author Jon Bentley
jaroslav@559	37	* @author Josh Bloch
jaroslav@559	38	*
jaroslav@559	39	* @version 2011.02.11 m765.827.12i:5\7pm
jaroslav@559	40	* @since 1.7
jaroslav@559	41	*/
jaroslav@559	42	final class DualPivotQuicksort {
jaroslav@559	43
jaroslav@559	44	/**
jaroslav@559	45	* Prevents instantiation.
jaroslav@559	46	*/
jaroslav@559	47	private DualPivotQuicksort() {}
jaroslav@559	48
jaroslav@559	49	/*
jaroslav@559	50	* Tuning parameters.
jaroslav@559	51	*/
jaroslav@559	52
jaroslav@559	53	/**
jaroslav@559	54	* The maximum number of runs in merge sort.
jaroslav@559	55	*/
jaroslav@559	56	private static final int MAX_RUN_COUNT = 67;
jaroslav@559	57
jaroslav@559	58	/**
jaroslav@559	59	* The maximum length of run in merge sort.
jaroslav@559	60	*/
jaroslav@559	61	private static final int MAX_RUN_LENGTH = 33;
jaroslav@559	62
jaroslav@559	63	/**
jaroslav@559	64	* If the length of an array to be sorted is less than this
jaroslav@559	65	* constant, Quicksort is used in preference to merge sort.
jaroslav@559	66	*/
jaroslav@559	67	private static final int QUICKSORT_THRESHOLD = 286;
jaroslav@559	68
jaroslav@559	69	/**
jaroslav@559	70	* If the length of an array to be sorted is less than this
jaroslav@559	71	* constant, insertion sort is used in preference to Quicksort.
jaroslav@559	72	*/
jaroslav@559	73	private static final int INSERTION_SORT_THRESHOLD = 47;
jaroslav@559	74
jaroslav@559	75	/**
jaroslav@559	76	* If the length of a byte array to be sorted is greater than this
jaroslav@559	77	* constant, counting sort is used in preference to insertion sort.
jaroslav@559	78	*/
jaroslav@559	79	private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
jaroslav@559	80
jaroslav@559	81	/**
jaroslav@559	82	* If the length of a short or char array to be sorted is greater
jaroslav@559	83	* than this constant, counting sort is used in preference to Quicksort.
jaroslav@559	84	*/
jaroslav@559	85	private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
jaroslav@559	86
jaroslav@559	87	/*
jaroslav@559	88	* Sorting methods for seven primitive types.
jaroslav@559	89	*/
jaroslav@559	90
jaroslav@559	91	/**
jaroslav@559	92	* Sorts the specified array.
jaroslav@559	93	*
jaroslav@559	94	* @param a the array to be sorted
jaroslav@559	95	*/
jaroslav@559	96	public static void sort(int[] a) {
jaroslav@559	97	sort(a, 0, a.length - 1);
jaroslav@559	98	}
jaroslav@559	99
jaroslav@559	100	/**
jaroslav@559	101	* Sorts the specified range of the array.
jaroslav@559	102	*
jaroslav@559	103	* @param a the array to be sorted
jaroslav@559	104	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	105	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	106	*/
jaroslav@559	107	public static void sort(int[] a, int left, int right) {
jaroslav@559	108	// Use Quicksort on small arrays
jaroslav@559	109	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	110	sort(a, left, right, true);
jaroslav@559	111	return;
jaroslav@559	112	}
jaroslav@559	113
jaroslav@559	114	/*
jaroslav@559	115	* Index run[i] is the start of i-th run
jaroslav@559	116	* (ascending or descending sequence).
jaroslav@559	117	*/
jaroslav@559	118	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	119	int count = 0; run[0] = left;
jaroslav@559	120
jaroslav@559	121	// Check if the array is nearly sorted
jaroslav@559	122	for (int k = left; k < right; run[count] = k) {
jaroslav@559	123	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	124	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	125	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	126	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	127	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	128	int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	129	}
jaroslav@559	130	} else { // equal
jaroslav@559	131	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	132	if (--m == 0) {
jaroslav@559	133	sort(a, left, right, true);
jaroslav@559	134	return;
jaroslav@559	135	}
jaroslav@559	136	}
jaroslav@559	137	}
jaroslav@559	138
jaroslav@559	139	/*
jaroslav@559	140	* The array is not highly structured,
jaroslav@559	141	* use Quicksort instead of merge sort.
jaroslav@559	142	*/
jaroslav@559	143	if (++count == MAX_RUN_COUNT) {
jaroslav@559	144	sort(a, left, right, true);
jaroslav@559	145	return;
jaroslav@559	146	}
jaroslav@559	147	}
jaroslav@559	148
jaroslav@559	149	// Check special cases
jaroslav@559	150	if (run[count] == right++) { // The last run contains one element
jaroslav@559	151	run[++count] = right;
jaroslav@559	152	} else if (count == 1) { // The array is already sorted
jaroslav@559	153	return;
jaroslav@559	154	}
jaroslav@559	155
jaroslav@559	156	/*
jaroslav@559	157	* Create temporary array, which is used for merging.
jaroslav@559	158	* Implementation note: variable "right" is increased by 1.
jaroslav@559	159	*/
jaroslav@559	160	int[] b; byte odd = 0;
jaroslav@559	161	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	162
jaroslav@559	163	if (odd == 0) {
jaroslav@559	164	b = a; a = new int[b.length];
jaroslav@559	165	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	166	} else {
jaroslav@559	167	b = new int[a.length];
jaroslav@559	168	}
jaroslav@559	169
jaroslav@559	170	// Merging
jaroslav@559	171	for (int last; count > 1; count = last) {
jaroslav@559	172	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	173	int hi = run[k], mi = run[k - 1];
jaroslav@559	174	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	175	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	176	b[i] = a[p++];
jaroslav@559	177	} else {
jaroslav@559	178	b[i] = a[q++];
jaroslav@559	179	}
jaroslav@559	180	}
jaroslav@559	181	run[++last] = hi;
jaroslav@559	182	}
jaroslav@559	183	if ((count & 1) != 0) {
jaroslav@559	184	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	185	b[i] = a[i]
jaroslav@559	186	);
jaroslav@559	187	run[++last] = right;
jaroslav@559	188	}
jaroslav@559	189	int[] t = a; a = b; b = t;
jaroslav@559	190	}
jaroslav@559	191	}
jaroslav@559	192
jaroslav@559	193	/**
jaroslav@559	194	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	195	*
jaroslav@559	196	* @param a the array to be sorted
jaroslav@559	197	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	198	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	199	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	200	*/
jaroslav@559	201	private static void sort(int[] a, int left, int right, boolean leftmost) {
jaroslav@559	202	int length = right - left + 1;
jaroslav@559	203
jaroslav@559	204	// Use insertion sort on tiny arrays
jaroslav@559	205	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	206	if (leftmost) {
jaroslav@559	207	/*
jaroslav@559	208	* Traditional (without sentinel) insertion sort,
jaroslav@559	209	* optimized for server VM, is used in case of
jaroslav@559	210	* the leftmost part.
jaroslav@559	211	*/
jaroslav@559	212	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	213	int ai = a[i + 1];
jaroslav@559	214	while (ai < a[j]) {
jaroslav@559	215	a[j + 1] = a[j];
jaroslav@559	216	if (j-- == left) {
jaroslav@559	217	break;
jaroslav@559	218	}
jaroslav@559	219	}
jaroslav@559	220	a[j + 1] = ai;
jaroslav@559	221	}
jaroslav@559	222	} else {
jaroslav@559	223	/*
jaroslav@559	224	* Skip the longest ascending sequence.
jaroslav@559	225	*/
jaroslav@559	226	do {
jaroslav@559	227	if (left >= right) {
jaroslav@559	228	return;
jaroslav@559	229	}
jaroslav@559	230	} while (a[++left] >= a[left - 1]);
jaroslav@559	231
jaroslav@559	232	/*
jaroslav@559	233	* Every element from adjoining part plays the role
jaroslav@559	234	* of sentinel, therefore this allows us to avoid the
jaroslav@559	235	* left range check on each iteration. Moreover, we use
jaroslav@559	236	* the more optimized algorithm, so called pair insertion
jaroslav@559	237	* sort, which is faster (in the context of Quicksort)
jaroslav@559	238	* than traditional implementation of insertion sort.
jaroslav@559	239	*/
jaroslav@559	240	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	241	int a1 = a[k], a2 = a[left];
jaroslav@559	242
jaroslav@559	243	if (a1 < a2) {
jaroslav@559	244	a2 = a1; a1 = a[left];
jaroslav@559	245	}
jaroslav@559	246	while (a1 < a[--k]) {
jaroslav@559	247	a[k + 2] = a[k];
jaroslav@559	248	}
jaroslav@559	249	a[++k + 1] = a1;
jaroslav@559	250
jaroslav@559	251	while (a2 < a[--k]) {
jaroslav@559	252	a[k + 1] = a[k];
jaroslav@559	253	}
jaroslav@559	254	a[k + 1] = a2;
jaroslav@559	255	}
jaroslav@559	256	int last = a[right];
jaroslav@559	257
jaroslav@559	258	while (last < a[--right]) {
jaroslav@559	259	a[right + 1] = a[right];
jaroslav@559	260	}
jaroslav@559	261	a[right + 1] = last;
jaroslav@559	262	}
jaroslav@559	263	return;
jaroslav@559	264	}
jaroslav@559	265
jaroslav@559	266	// Inexpensive approximation of length / 7
jaroslav@559	267	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	268
jaroslav@559	269	/*
jaroslav@559	270	* Sort five evenly spaced elements around (and including) the
jaroslav@559	271	* center element in the range. These elements will be used for
jaroslav@559	272	* pivot selection as described below. The choice for spacing
jaroslav@559	273	* these elements was empirically determined to work well on
jaroslav@559	274	* a wide variety of inputs.
jaroslav@559	275	*/
jaroslav@559	276	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	277	int e2 = e3 - seventh;
jaroslav@559	278	int e1 = e2 - seventh;
jaroslav@559	279	int e4 = e3 + seventh;
jaroslav@559	280	int e5 = e4 + seventh;
jaroslav@559	281
jaroslav@559	282	// Sort these elements using insertion sort
jaroslav@559	283	if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	284
jaroslav@559	285	if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	286	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	287	}
jaroslav@559	288	if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	289	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	290	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	291	}
jaroslav@559	292	}
jaroslav@559	293	if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	294	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	295	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	296	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	297	}
jaroslav@559	298	}
jaroslav@559	299	}
jaroslav@559	300
jaroslav@559	301	// Pointers
jaroslav@559	302	int less = left; // The index of the first element of center part
jaroslav@559	303	int great = right; // The index before the first element of right part
jaroslav@559	304
jaroslav@559	305	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	306	/*
jaroslav@559	307	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	308	* These values are inexpensive approximations of the first and
jaroslav@559	309	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	310	*/
jaroslav@559	311	int pivot1 = a[e2];
jaroslav@559	312	int pivot2 = a[e4];
jaroslav@559	313
jaroslav@559	314	/*
jaroslav@559	315	* The first and the last elements to be sorted are moved to the
jaroslav@559	316	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	317	* is complete, the pivots are swapped back into their final
jaroslav@559	318	* positions, and excluded from subsequent sorting.
jaroslav@559	319	*/
jaroslav@559	320	a[e2] = a[left];
jaroslav@559	321	a[e4] = a[right];
jaroslav@559	322
jaroslav@559	323	/*
jaroslav@559	324	* Skip elements, which are less or greater than pivot values.
jaroslav@559	325	*/
jaroslav@559	326	while (a[++less] < pivot1);
jaroslav@559	327	while (a[--great] > pivot2);
jaroslav@559	328
jaroslav@559	329	/*
jaroslav@559	330	* Partitioning:
jaroslav@559	331	*
jaroslav@559	332	* left part center part right part
jaroslav@559	333	* +--------------------------------------------------------------+
jaroslav@559	334	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	335	* +--------------------------------------------------------------+
jaroslav@559	336	* ^ ^ ^
jaroslav@559	337	* \| \| \|
jaroslav@559	338	* less k great
jaroslav@559	339	*
jaroslav@559	340	* Invariants:
jaroslav@559	341	*
jaroslav@559	342	* all in (left, less) < pivot1
jaroslav@559	343	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	344	* all in (great, right) > pivot2
jaroslav@559	345	*
jaroslav@559	346	* Pointer k is the first index of ?-part.
jaroslav@559	347	*/
jaroslav@559	348	outer:
jaroslav@559	349	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	350	int ak = a[k];
jaroslav@559	351	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	352	a[k] = a[less];
jaroslav@559	353	/*
jaroslav@559	354	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	355	* of "a[i++] = b;" due to performance issue.
jaroslav@559	356	*/
jaroslav@559	357	a[less] = ak;
jaroslav@559	358	++less;
jaroslav@559	359	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	360	while (a[great] > pivot2) {
jaroslav@559	361	if (great-- == k) {
jaroslav@559	362	break outer;
jaroslav@559	363	}
jaroslav@559	364	}
jaroslav@559	365	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	366	a[k] = a[less];
jaroslav@559	367	a[less] = a[great];
jaroslav@559	368	++less;
jaroslav@559	369	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	370	a[k] = a[great];
jaroslav@559	371	}
jaroslav@559	372	/*
jaroslav@559	373	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	374	* of "a[i--] = b;" due to performance issue.
jaroslav@559	375	*/
jaroslav@559	376	a[great] = ak;
jaroslav@559	377	--great;
jaroslav@559	378	}
jaroslav@559	379	}
jaroslav@559	380
jaroslav@559	381	// Swap pivots into their final positions
jaroslav@559	382	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	383	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	384
jaroslav@559	385	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	386	sort(a, left, less - 2, leftmost);
jaroslav@559	387	sort(a, great + 2, right, false);
jaroslav@559	388
jaroslav@559	389	/*
jaroslav@559	390	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	391	* swap internal pivot values to ends.
jaroslav@559	392	*/
jaroslav@559	393	if (less < e1 && e5 < great) {
jaroslav@559	394	/*
jaroslav@559	395	* Skip elements, which are equal to pivot values.
jaroslav@559	396	*/
jaroslav@559	397	while (a[less] == pivot1) {
jaroslav@559	398	++less;
jaroslav@559	399	}
jaroslav@559	400
jaroslav@559	401	while (a[great] == pivot2) {
jaroslav@559	402	--great;
jaroslav@559	403	}
jaroslav@559	404
jaroslav@559	405	/*
jaroslav@559	406	* Partitioning:
jaroslav@559	407	*
jaroslav@559	408	* left part center part right part
jaroslav@559	409	* +----------------------------------------------------------+
jaroslav@559	410	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	411	* +----------------------------------------------------------+
jaroslav@559	412	* ^ ^ ^
jaroslav@559	413	* \| \| \|
jaroslav@559	414	* less k great
jaroslav@559	415	*
jaroslav@559	416	* Invariants:
jaroslav@559	417	*
jaroslav@559	418	* all in (*, less) == pivot1
jaroslav@559	419	* pivot1 < all in [less, k) < pivot2
jaroslav@559	420	* all in (great, *) == pivot2
jaroslav@559	421	*
jaroslav@559	422	* Pointer k is the first index of ?-part.
jaroslav@559	423	*/
jaroslav@559	424	outer:
jaroslav@559	425	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	426	int ak = a[k];
jaroslav@559	427	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	428	a[k] = a[less];
jaroslav@559	429	a[less] = ak;
jaroslav@559	430	++less;
jaroslav@559	431	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	432	while (a[great] == pivot2) {
jaroslav@559	433	if (great-- == k) {
jaroslav@559	434	break outer;
jaroslav@559	435	}
jaroslav@559	436	}
jaroslav@559	437	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	438	a[k] = a[less];
jaroslav@559	439	/*
jaroslav@559	440	* Even though a[great] equals to pivot1, the
jaroslav@559	441	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	442	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	443	* of different signs. Therefore in float and
jaroslav@559	444	* double sorting methods we have to use more
jaroslav@559	445	* accurate assignment a[less] = a[great].
jaroslav@559	446	*/
jaroslav@559	447	a[less] = pivot1;
jaroslav@559	448	++less;
jaroslav@559	449	} else { // pivot1 < a[great] < pivot2
jaroslav@559	450	a[k] = a[great];
jaroslav@559	451	}
jaroslav@559	452	a[great] = ak;
jaroslav@559	453	--great;
jaroslav@559	454	}
jaroslav@559	455	}
jaroslav@559	456	}
jaroslav@559	457
jaroslav@559	458	// Sort center part recursively
jaroslav@559	459	sort(a, less, great, false);
jaroslav@559	460
jaroslav@559	461	} else { // Partitioning with one pivot
jaroslav@559	462	/*
jaroslav@559	463	* Use the third of the five sorted elements as pivot.
jaroslav@559	464	* This value is inexpensive approximation of the median.
jaroslav@559	465	*/
jaroslav@559	466	int pivot = a[e3];
jaroslav@559	467
jaroslav@559	468	/*
jaroslav@559	469	* Partitioning degenerates to the traditional 3-way
jaroslav@559	470	* (or "Dutch National Flag") schema:
jaroslav@559	471	*
jaroslav@559	472	* left part center part right part
jaroslav@559	473	* +-------------------------------------------------+
jaroslav@559	474	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	475	* +-------------------------------------------------+
jaroslav@559	476	* ^ ^ ^
jaroslav@559	477	* \| \| \|
jaroslav@559	478	* less k great
jaroslav@559	479	*
jaroslav@559	480	* Invariants:
jaroslav@559	481	*
jaroslav@559	482	* all in (left, less) < pivot
jaroslav@559	483	* all in [less, k) == pivot
jaroslav@559	484	* all in (great, right) > pivot
jaroslav@559	485	*
jaroslav@559	486	* Pointer k is the first index of ?-part.
jaroslav@559	487	*/
jaroslav@559	488	for (int k = less; k <= great; ++k) {
jaroslav@559	489	if (a[k] == pivot) {
jaroslav@559	490	continue;
jaroslav@559	491	}
jaroslav@559	492	int ak = a[k];
jaroslav@559	493	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	494	a[k] = a[less];
jaroslav@559	495	a[less] = ak;
jaroslav@559	496	++less;
jaroslav@559	497	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	498	while (a[great] > pivot) {
jaroslav@559	499	--great;
jaroslav@559	500	}
jaroslav@559	501	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	502	a[k] = a[less];
jaroslav@559	503	a[less] = a[great];
jaroslav@559	504	++less;
jaroslav@559	505	} else { // a[great] == pivot
jaroslav@559	506	/*
jaroslav@559	507	* Even though a[great] equals to pivot, the
jaroslav@559	508	* assignment a[k] = pivot may be incorrect,
jaroslav@559	509	* if a[great] and pivot are floating-point
jaroslav@559	510	* zeros of different signs. Therefore in float
jaroslav@559	511	* and double sorting methods we have to use
jaroslav@559	512	* more accurate assignment a[k] = a[great].
jaroslav@559	513	*/
jaroslav@559	514	a[k] = pivot;
jaroslav@559	515	}
jaroslav@559	516	a[great] = ak;
jaroslav@559	517	--great;
jaroslav@559	518	}
jaroslav@559	519	}
jaroslav@559	520
jaroslav@559	521	/*
jaroslav@559	522	* Sort left and right parts recursively.
jaroslav@559	523	* All elements from center part are equal
jaroslav@559	524	* and, therefore, already sorted.
jaroslav@559	525	*/
jaroslav@559	526	sort(a, left, less - 1, leftmost);
jaroslav@559	527	sort(a, great + 1, right, false);
jaroslav@559	528	}
jaroslav@559	529	}
jaroslav@559	530
jaroslav@559	531	/**
jaroslav@559	532	* Sorts the specified array.
jaroslav@559	533	*
jaroslav@559	534	* @param a the array to be sorted
jaroslav@559	535	*/
jaroslav@559	536	public static void sort(long[] a) {
jaroslav@559	537	sort(a, 0, a.length - 1);
jaroslav@559	538	}
jaroslav@559	539
jaroslav@559	540	/**
jaroslav@559	541	* Sorts the specified range of the array.
jaroslav@559	542	*
jaroslav@559	543	* @param a the array to be sorted
jaroslav@559	544	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	545	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	546	*/
jaroslav@559	547	public static void sort(long[] a, int left, int right) {
jaroslav@559	548	// Use Quicksort on small arrays
jaroslav@559	549	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	550	sort(a, left, right, true);
jaroslav@559	551	return;
jaroslav@559	552	}
jaroslav@559	553
jaroslav@559	554	/*
jaroslav@559	555	* Index run[i] is the start of i-th run
jaroslav@559	556	* (ascending or descending sequence).
jaroslav@559	557	*/
jaroslav@559	558	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	559	int count = 0; run[0] = left;
jaroslav@559	560
jaroslav@559	561	// Check if the array is nearly sorted
jaroslav@559	562	for (int k = left; k < right; run[count] = k) {
jaroslav@559	563	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	564	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	565	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	566	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	567	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	568	long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	569	}
jaroslav@559	570	} else { // equal
jaroslav@559	571	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	572	if (--m == 0) {
jaroslav@559	573	sort(a, left, right, true);
jaroslav@559	574	return;
jaroslav@559	575	}
jaroslav@559	576	}
jaroslav@559	577	}
jaroslav@559	578
jaroslav@559	579	/*
jaroslav@559	580	* The array is not highly structured,
jaroslav@559	581	* use Quicksort instead of merge sort.
jaroslav@559	582	*/
jaroslav@559	583	if (++count == MAX_RUN_COUNT) {
jaroslav@559	584	sort(a, left, right, true);
jaroslav@559	585	return;
jaroslav@559	586	}
jaroslav@559	587	}
jaroslav@559	588
jaroslav@559	589	// Check special cases
jaroslav@559	590	if (run[count] == right++) { // The last run contains one element
jaroslav@559	591	run[++count] = right;
jaroslav@559	592	} else if (count == 1) { // The array is already sorted
jaroslav@559	593	return;
jaroslav@559	594	}
jaroslav@559	595
jaroslav@559	596	/*
jaroslav@559	597	* Create temporary array, which is used for merging.
jaroslav@559	598	* Implementation note: variable "right" is increased by 1.
jaroslav@559	599	*/
jaroslav@559	600	long[] b; byte odd = 0;
jaroslav@559	601	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	602
jaroslav@559	603	if (odd == 0) {
jaroslav@559	604	b = a; a = new long[b.length];
jaroslav@559	605	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	606	} else {
jaroslav@559	607	b = new long[a.length];
jaroslav@559	608	}
jaroslav@559	609
jaroslav@559	610	// Merging
jaroslav@559	611	for (int last; count > 1; count = last) {
jaroslav@559	612	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	613	int hi = run[k], mi = run[k - 1];
jaroslav@559	614	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	615	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	616	b[i] = a[p++];
jaroslav@559	617	} else {
jaroslav@559	618	b[i] = a[q++];
jaroslav@559	619	}
jaroslav@559	620	}
jaroslav@559	621	run[++last] = hi;
jaroslav@559	622	}
jaroslav@559	623	if ((count & 1) != 0) {
jaroslav@559	624	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	625	b[i] = a[i]
jaroslav@559	626	);
jaroslav@559	627	run[++last] = right;
jaroslav@559	628	}
jaroslav@559	629	long[] t = a; a = b; b = t;
jaroslav@559	630	}
jaroslav@559	631	}
jaroslav@559	632
jaroslav@559	633	/**
jaroslav@559	634	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	635	*
jaroslav@559	636	* @param a the array to be sorted
jaroslav@559	637	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	638	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	639	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	640	*/
jaroslav@559	641	private static void sort(long[] a, int left, int right, boolean leftmost) {
jaroslav@559	642	int length = right - left + 1;
jaroslav@559	643
jaroslav@559	644	// Use insertion sort on tiny arrays
jaroslav@559	645	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	646	if (leftmost) {
jaroslav@559	647	/*
jaroslav@559	648	* Traditional (without sentinel) insertion sort,
jaroslav@559	649	* optimized for server VM, is used in case of
jaroslav@559	650	* the leftmost part.
jaroslav@559	651	*/
jaroslav@559	652	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	653	long ai = a[i + 1];
jaroslav@559	654	while (ai < a[j]) {
jaroslav@559	655	a[j + 1] = a[j];
jaroslav@559	656	if (j-- == left) {
jaroslav@559	657	break;
jaroslav@559	658	}
jaroslav@559	659	}
jaroslav@559	660	a[j + 1] = ai;
jaroslav@559	661	}
jaroslav@559	662	} else {
jaroslav@559	663	/*
jaroslav@559	664	* Skip the longest ascending sequence.
jaroslav@559	665	*/
jaroslav@559	666	do {
jaroslav@559	667	if (left >= right) {
jaroslav@559	668	return;
jaroslav@559	669	}
jaroslav@559	670	} while (a[++left] >= a[left - 1]);
jaroslav@559	671
jaroslav@559	672	/*
jaroslav@559	673	* Every element from adjoining part plays the role
jaroslav@559	674	* of sentinel, therefore this allows us to avoid the
jaroslav@559	675	* left range check on each iteration. Moreover, we use
jaroslav@559	676	* the more optimized algorithm, so called pair insertion
jaroslav@559	677	* sort, which is faster (in the context of Quicksort)
jaroslav@559	678	* than traditional implementation of insertion sort.
jaroslav@559	679	*/
jaroslav@559	680	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	681	long a1 = a[k], a2 = a[left];
jaroslav@559	682
jaroslav@559	683	if (a1 < a2) {
jaroslav@559	684	a2 = a1; a1 = a[left];
jaroslav@559	685	}
jaroslav@559	686	while (a1 < a[--k]) {
jaroslav@559	687	a[k + 2] = a[k];
jaroslav@559	688	}
jaroslav@559	689	a[++k + 1] = a1;
jaroslav@559	690
jaroslav@559	691	while (a2 < a[--k]) {
jaroslav@559	692	a[k + 1] = a[k];
jaroslav@559	693	}
jaroslav@559	694	a[k + 1] = a2;
jaroslav@559	695	}
jaroslav@559	696	long last = a[right];
jaroslav@559	697
jaroslav@559	698	while (last < a[--right]) {
jaroslav@559	699	a[right + 1] = a[right];
jaroslav@559	700	}
jaroslav@559	701	a[right + 1] = last;
jaroslav@559	702	}
jaroslav@559	703	return;
jaroslav@559	704	}
jaroslav@559	705
jaroslav@559	706	// Inexpensive approximation of length / 7
jaroslav@559	707	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	708
jaroslav@559	709	/*
jaroslav@559	710	* Sort five evenly spaced elements around (and including) the
jaroslav@559	711	* center element in the range. These elements will be used for
jaroslav@559	712	* pivot selection as described below. The choice for spacing
jaroslav@559	713	* these elements was empirically determined to work well on
jaroslav@559	714	* a wide variety of inputs.
jaroslav@559	715	*/
jaroslav@559	716	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	717	int e2 = e3 - seventh;
jaroslav@559	718	int e1 = e2 - seventh;
jaroslav@559	719	int e4 = e3 + seventh;
jaroslav@559	720	int e5 = e4 + seventh;
jaroslav@559	721
jaroslav@559	722	// Sort these elements using insertion sort
jaroslav@559	723	if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	724
jaroslav@559	725	if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	726	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	727	}
jaroslav@559	728	if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	729	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	730	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	731	}
jaroslav@559	732	}
jaroslav@559	733	if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	734	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	735	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	736	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	737	}
jaroslav@559	738	}
jaroslav@559	739	}
jaroslav@559	740
jaroslav@559	741	// Pointers
jaroslav@559	742	int less = left; // The index of the first element of center part
jaroslav@559	743	int great = right; // The index before the first element of right part
jaroslav@559	744
jaroslav@559	745	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	746	/*
jaroslav@559	747	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	748	* These values are inexpensive approximations of the first and
jaroslav@559	749	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	750	*/
jaroslav@559	751	long pivot1 = a[e2];
jaroslav@559	752	long pivot2 = a[e4];
jaroslav@559	753
jaroslav@559	754	/*
jaroslav@559	755	* The first and the last elements to be sorted are moved to the
jaroslav@559	756	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	757	* is complete, the pivots are swapped back into their final
jaroslav@559	758	* positions, and excluded from subsequent sorting.
jaroslav@559	759	*/
jaroslav@559	760	a[e2] = a[left];
jaroslav@559	761	a[e4] = a[right];
jaroslav@559	762
jaroslav@559	763	/*
jaroslav@559	764	* Skip elements, which are less or greater than pivot values.
jaroslav@559	765	*/
jaroslav@559	766	while (a[++less] < pivot1);
jaroslav@559	767	while (a[--great] > pivot2);
jaroslav@559	768
jaroslav@559	769	/*
jaroslav@559	770	* Partitioning:
jaroslav@559	771	*
jaroslav@559	772	* left part center part right part
jaroslav@559	773	* +--------------------------------------------------------------+
jaroslav@559	774	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	775	* +--------------------------------------------------------------+
jaroslav@559	776	* ^ ^ ^
jaroslav@559	777	* \| \| \|
jaroslav@559	778	* less k great
jaroslav@559	779	*
jaroslav@559	780	* Invariants:
jaroslav@559	781	*
jaroslav@559	782	* all in (left, less) < pivot1
jaroslav@559	783	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	784	* all in (great, right) > pivot2
jaroslav@559	785	*
jaroslav@559	786	* Pointer k is the first index of ?-part.
jaroslav@559	787	*/
jaroslav@559	788	outer:
jaroslav@559	789	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	790	long ak = a[k];
jaroslav@559	791	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	792	a[k] = a[less];
jaroslav@559	793	/*
jaroslav@559	794	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	795	* of "a[i++] = b;" due to performance issue.
jaroslav@559	796	*/
jaroslav@559	797	a[less] = ak;
jaroslav@559	798	++less;
jaroslav@559	799	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	800	while (a[great] > pivot2) {
jaroslav@559	801	if (great-- == k) {
jaroslav@559	802	break outer;
jaroslav@559	803	}
jaroslav@559	804	}
jaroslav@559	805	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	806	a[k] = a[less];
jaroslav@559	807	a[less] = a[great];
jaroslav@559	808	++less;
jaroslav@559	809	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	810	a[k] = a[great];
jaroslav@559	811	}
jaroslav@559	812	/*
jaroslav@559	813	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	814	* of "a[i--] = b;" due to performance issue.
jaroslav@559	815	*/
jaroslav@559	816	a[great] = ak;
jaroslav@559	817	--great;
jaroslav@559	818	}
jaroslav@559	819	}
jaroslav@559	820
jaroslav@559	821	// Swap pivots into their final positions
jaroslav@559	822	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	823	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	824
jaroslav@559	825	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	826	sort(a, left, less - 2, leftmost);
jaroslav@559	827	sort(a, great + 2, right, false);
jaroslav@559	828
jaroslav@559	829	/*
jaroslav@559	830	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	831	* swap internal pivot values to ends.
jaroslav@559	832	*/
jaroslav@559	833	if (less < e1 && e5 < great) {
jaroslav@559	834	/*
jaroslav@559	835	* Skip elements, which are equal to pivot values.
jaroslav@559	836	*/
jaroslav@559	837	while (a[less] == pivot1) {
jaroslav@559	838	++less;
jaroslav@559	839	}
jaroslav@559	840
jaroslav@559	841	while (a[great] == pivot2) {
jaroslav@559	842	--great;
jaroslav@559	843	}
jaroslav@559	844
jaroslav@559	845	/*
jaroslav@559	846	* Partitioning:
jaroslav@559	847	*
jaroslav@559	848	* left part center part right part
jaroslav@559	849	* +----------------------------------------------------------+
jaroslav@559	850	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	851	* +----------------------------------------------------------+
jaroslav@559	852	* ^ ^ ^
jaroslav@559	853	* \| \| \|
jaroslav@559	854	* less k great
jaroslav@559	855	*
jaroslav@559	856	* Invariants:
jaroslav@559	857	*
jaroslav@559	858	* all in (*, less) == pivot1
jaroslav@559	859	* pivot1 < all in [less, k) < pivot2
jaroslav@559	860	* all in (great, *) == pivot2
jaroslav@559	861	*
jaroslav@559	862	* Pointer k is the first index of ?-part.
jaroslav@559	863	*/
jaroslav@559	864	outer:
jaroslav@559	865	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	866	long ak = a[k];
jaroslav@559	867	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	868	a[k] = a[less];
jaroslav@559	869	a[less] = ak;
jaroslav@559	870	++less;
jaroslav@559	871	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	872	while (a[great] == pivot2) {
jaroslav@559	873	if (great-- == k) {
jaroslav@559	874	break outer;
jaroslav@559	875	}
jaroslav@559	876	}
jaroslav@559	877	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	878	a[k] = a[less];
jaroslav@559	879	/*
jaroslav@559	880	* Even though a[great] equals to pivot1, the
jaroslav@559	881	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	882	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	883	* of different signs. Therefore in float and
jaroslav@559	884	* double sorting methods we have to use more
jaroslav@559	885	* accurate assignment a[less] = a[great].
jaroslav@559	886	*/
jaroslav@559	887	a[less] = pivot1;
jaroslav@559	888	++less;
jaroslav@559	889	} else { // pivot1 < a[great] < pivot2
jaroslav@559	890	a[k] = a[great];
jaroslav@559	891	}
jaroslav@559	892	a[great] = ak;
jaroslav@559	893	--great;
jaroslav@559	894	}
jaroslav@559	895	}
jaroslav@559	896	}
jaroslav@559	897
jaroslav@559	898	// Sort center part recursively
jaroslav@559	899	sort(a, less, great, false);
jaroslav@559	900
jaroslav@559	901	} else { // Partitioning with one pivot
jaroslav@559	902	/*
jaroslav@559	903	* Use the third of the five sorted elements as pivot.
jaroslav@559	904	* This value is inexpensive approximation of the median.
jaroslav@559	905	*/
jaroslav@559	906	long pivot = a[e3];
jaroslav@559	907
jaroslav@559	908	/*
jaroslav@559	909	* Partitioning degenerates to the traditional 3-way
jaroslav@559	910	* (or "Dutch National Flag") schema:
jaroslav@559	911	*
jaroslav@559	912	* left part center part right part
jaroslav@559	913	* +-------------------------------------------------+
jaroslav@559	914	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	915	* +-------------------------------------------------+
jaroslav@559	916	* ^ ^ ^
jaroslav@559	917	* \| \| \|
jaroslav@559	918	* less k great
jaroslav@559	919	*
jaroslav@559	920	* Invariants:
jaroslav@559	921	*
jaroslav@559	922	* all in (left, less) < pivot
jaroslav@559	923	* all in [less, k) == pivot
jaroslav@559	924	* all in (great, right) > pivot
jaroslav@559	925	*
jaroslav@559	926	* Pointer k is the first index of ?-part.
jaroslav@559	927	*/
jaroslav@559	928	for (int k = less; k <= great; ++k) {
jaroslav@559	929	if (a[k] == pivot) {
jaroslav@559	930	continue;
jaroslav@559	931	}
jaroslav@559	932	long ak = a[k];
jaroslav@559	933	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	934	a[k] = a[less];
jaroslav@559	935	a[less] = ak;
jaroslav@559	936	++less;
jaroslav@559	937	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	938	while (a[great] > pivot) {
jaroslav@559	939	--great;
jaroslav@559	940	}
jaroslav@559	941	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	942	a[k] = a[less];
jaroslav@559	943	a[less] = a[great];
jaroslav@559	944	++less;
jaroslav@559	945	} else { // a[great] == pivot
jaroslav@559	946	/*
jaroslav@559	947	* Even though a[great] equals to pivot, the
jaroslav@559	948	* assignment a[k] = pivot may be incorrect,
jaroslav@559	949	* if a[great] and pivot are floating-point
jaroslav@559	950	* zeros of different signs. Therefore in float
jaroslav@559	951	* and double sorting methods we have to use
jaroslav@559	952	* more accurate assignment a[k] = a[great].
jaroslav@559	953	*/
jaroslav@559	954	a[k] = pivot;
jaroslav@559	955	}
jaroslav@559	956	a[great] = ak;
jaroslav@559	957	--great;
jaroslav@559	958	}
jaroslav@559	959	}
jaroslav@559	960
jaroslav@559	961	/*
jaroslav@559	962	* Sort left and right parts recursively.
jaroslav@559	963	* All elements from center part are equal
jaroslav@559	964	* and, therefore, already sorted.
jaroslav@559	965	*/
jaroslav@559	966	sort(a, left, less - 1, leftmost);
jaroslav@559	967	sort(a, great + 1, right, false);
jaroslav@559	968	}
jaroslav@559	969	}
jaroslav@559	970
jaroslav@559	971	/**
jaroslav@559	972	* Sorts the specified array.
jaroslav@559	973	*
jaroslav@559	974	* @param a the array to be sorted
jaroslav@559	975	*/
jaroslav@559	976	public static void sort(short[] a) {
jaroslav@559	977	sort(a, 0, a.length - 1);
jaroslav@559	978	}
jaroslav@559	979
jaroslav@559	980	/**
jaroslav@559	981	* Sorts the specified range of the array.
jaroslav@559	982	*
jaroslav@559	983	* @param a the array to be sorted
jaroslav@559	984	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	985	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	986	*/
jaroslav@559	987	public static void sort(short[] a, int left, int right) {
jaroslav@559	988	// Use counting sort on large arrays
jaroslav@559	989	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
jaroslav@559	990	int[] count = new int[NUM_SHORT_VALUES];
jaroslav@559	991
jaroslav@559	992	for (int i = left - 1; ++i <= right;
jaroslav@559	993	count[a[i] - Short.MIN_VALUE]++
jaroslav@559	994	);
jaroslav@559	995	for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
jaroslav@559	996	while (count[--i] == 0);
jaroslav@559	997	short value = (short) (i + Short.MIN_VALUE);
jaroslav@559	998	int s = count[i];
jaroslav@559	999
jaroslav@559	1000	do {
jaroslav@559	1001	a[--k] = value;
jaroslav@559	1002	} while (--s > 0);
jaroslav@559	1003	}
jaroslav@559	1004	} else { // Use Dual-Pivot Quicksort on small arrays
jaroslav@559	1005	doSort(a, left, right);
jaroslav@559	1006	}
jaroslav@559	1007	}
jaroslav@559	1008
jaroslav@559	1009	/** The number of distinct short values. */
jaroslav@559	1010	private static final int NUM_SHORT_VALUES = 1 << 16;
jaroslav@559	1011
jaroslav@559	1012	/**
jaroslav@559	1013	* Sorts the specified range of the array.
jaroslav@559	1014	*
jaroslav@559	1015	* @param a the array to be sorted
jaroslav@559	1016	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1017	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1018	*/
jaroslav@559	1019	private static void doSort(short[] a, int left, int right) {
jaroslav@559	1020	// Use Quicksort on small arrays
jaroslav@559	1021	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	1022	sort(a, left, right, true);
jaroslav@559	1023	return;
jaroslav@559	1024	}
jaroslav@559	1025
jaroslav@559	1026	/*
jaroslav@559	1027	* Index run[i] is the start of i-th run
jaroslav@559	1028	* (ascending or descending sequence).
jaroslav@559	1029	*/
jaroslav@559	1030	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	1031	int count = 0; run[0] = left;
jaroslav@559	1032
jaroslav@559	1033	// Check if the array is nearly sorted
jaroslav@559	1034	for (int k = left; k < right; run[count] = k) {
jaroslav@559	1035	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	1036	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	1037	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	1038	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	1039	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	1040	short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	1041	}
jaroslav@559	1042	} else { // equal
jaroslav@559	1043	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	1044	if (--m == 0) {
jaroslav@559	1045	sort(a, left, right, true);
jaroslav@559	1046	return;
jaroslav@559	1047	}
jaroslav@559	1048	}
jaroslav@559	1049	}
jaroslav@559	1050
jaroslav@559	1051	/*
jaroslav@559	1052	* The array is not highly structured,
jaroslav@559	1053	* use Quicksort instead of merge sort.
jaroslav@559	1054	*/
jaroslav@559	1055	if (++count == MAX_RUN_COUNT) {
jaroslav@559	1056	sort(a, left, right, true);
jaroslav@559	1057	return;
jaroslav@559	1058	}
jaroslav@559	1059	}
jaroslav@559	1060
jaroslav@559	1061	// Check special cases
jaroslav@559	1062	if (run[count] == right++) { // The last run contains one element
jaroslav@559	1063	run[++count] = right;
jaroslav@559	1064	} else if (count == 1) { // The array is already sorted
jaroslav@559	1065	return;
jaroslav@559	1066	}
jaroslav@559	1067
jaroslav@559	1068	/*
jaroslav@559	1069	* Create temporary array, which is used for merging.
jaroslav@559	1070	* Implementation note: variable "right" is increased by 1.
jaroslav@559	1071	*/
jaroslav@559	1072	short[] b; byte odd = 0;
jaroslav@559	1073	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	1074
jaroslav@559	1075	if (odd == 0) {
jaroslav@559	1076	b = a; a = new short[b.length];
jaroslav@559	1077	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	1078	} else {
jaroslav@559	1079	b = new short[a.length];
jaroslav@559	1080	}
jaroslav@559	1081
jaroslav@559	1082	// Merging
jaroslav@559	1083	for (int last; count > 1; count = last) {
jaroslav@559	1084	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	1085	int hi = run[k], mi = run[k - 1];
jaroslav@559	1086	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	1087	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	1088	b[i] = a[p++];
jaroslav@559	1089	} else {
jaroslav@559	1090	b[i] = a[q++];
jaroslav@559	1091	}
jaroslav@559	1092	}
jaroslav@559	1093	run[++last] = hi;
jaroslav@559	1094	}
jaroslav@559	1095	if ((count & 1) != 0) {
jaroslav@559	1096	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	1097	b[i] = a[i]
jaroslav@559	1098	);
jaroslav@559	1099	run[++last] = right;
jaroslav@559	1100	}
jaroslav@559	1101	short[] t = a; a = b; b = t;
jaroslav@559	1102	}
jaroslav@559	1103	}
jaroslav@559	1104
jaroslav@559	1105	/**
jaroslav@559	1106	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	1107	*
jaroslav@559	1108	* @param a the array to be sorted
jaroslav@559	1109	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1110	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1111	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	1112	*/
jaroslav@559	1113	private static void sort(short[] a, int left, int right, boolean leftmost) {
jaroslav@559	1114	int length = right - left + 1;
jaroslav@559	1115
jaroslav@559	1116	// Use insertion sort on tiny arrays
jaroslav@559	1117	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	1118	if (leftmost) {
jaroslav@559	1119	/*
jaroslav@559	1120	* Traditional (without sentinel) insertion sort,
jaroslav@559	1121	* optimized for server VM, is used in case of
jaroslav@559	1122	* the leftmost part.
jaroslav@559	1123	*/
jaroslav@559	1124	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	1125	short ai = a[i + 1];
jaroslav@559	1126	while (ai < a[j]) {
jaroslav@559	1127	a[j + 1] = a[j];
jaroslav@559	1128	if (j-- == left) {
jaroslav@559	1129	break;
jaroslav@559	1130	}
jaroslav@559	1131	}
jaroslav@559	1132	a[j + 1] = ai;
jaroslav@559	1133	}
jaroslav@559	1134	} else {
jaroslav@559	1135	/*
jaroslav@559	1136	* Skip the longest ascending sequence.
jaroslav@559	1137	*/
jaroslav@559	1138	do {
jaroslav@559	1139	if (left >= right) {
jaroslav@559	1140	return;
jaroslav@559	1141	}
jaroslav@559	1142	} while (a[++left] >= a[left - 1]);
jaroslav@559	1143
jaroslav@559	1144	/*
jaroslav@559	1145	* Every element from adjoining part plays the role
jaroslav@559	1146	* of sentinel, therefore this allows us to avoid the
jaroslav@559	1147	* left range check on each iteration. Moreover, we use
jaroslav@559	1148	* the more optimized algorithm, so called pair insertion
jaroslav@559	1149	* sort, which is faster (in the context of Quicksort)
jaroslav@559	1150	* than traditional implementation of insertion sort.
jaroslav@559	1151	*/
jaroslav@559	1152	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	1153	short a1 = a[k], a2 = a[left];
jaroslav@559	1154
jaroslav@559	1155	if (a1 < a2) {
jaroslav@559	1156	a2 = a1; a1 = a[left];
jaroslav@559	1157	}
jaroslav@559	1158	while (a1 < a[--k]) {
jaroslav@559	1159	a[k + 2] = a[k];
jaroslav@559	1160	}
jaroslav@559	1161	a[++k + 1] = a1;
jaroslav@559	1162
jaroslav@559	1163	while (a2 < a[--k]) {
jaroslav@559	1164	a[k + 1] = a[k];
jaroslav@559	1165	}
jaroslav@559	1166	a[k + 1] = a2;
jaroslav@559	1167	}
jaroslav@559	1168	short last = a[right];
jaroslav@559	1169
jaroslav@559	1170	while (last < a[--right]) {
jaroslav@559	1171	a[right + 1] = a[right];
jaroslav@559	1172	}
jaroslav@559	1173	a[right + 1] = last;
jaroslav@559	1174	}
jaroslav@559	1175	return;
jaroslav@559	1176	}
jaroslav@559	1177
jaroslav@559	1178	// Inexpensive approximation of length / 7
jaroslav@559	1179	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	1180
jaroslav@559	1181	/*
jaroslav@559	1182	* Sort five evenly spaced elements around (and including) the
jaroslav@559	1183	* center element in the range. These elements will be used for
jaroslav@559	1184	* pivot selection as described below. The choice for spacing
jaroslav@559	1185	* these elements was empirically determined to work well on
jaroslav@559	1186	* a wide variety of inputs.
jaroslav@559	1187	*/
jaroslav@559	1188	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	1189	int e2 = e3 - seventh;
jaroslav@559	1190	int e1 = e2 - seventh;
jaroslav@559	1191	int e4 = e3 + seventh;
jaroslav@559	1192	int e5 = e4 + seventh;
jaroslav@559	1193
jaroslav@559	1194	// Sort these elements using insertion sort
jaroslav@559	1195	if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1196
jaroslav@559	1197	if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1198	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1199	}
jaroslav@559	1200	if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	1201	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1202	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1203	}
jaroslav@559	1204	}
jaroslav@559	1205	if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	1206	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	1207	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1208	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1209	}
jaroslav@559	1210	}
jaroslav@559	1211	}
jaroslav@559	1212
jaroslav@559	1213	// Pointers
jaroslav@559	1214	int less = left; // The index of the first element of center part
jaroslav@559	1215	int great = right; // The index before the first element of right part
jaroslav@559	1216
jaroslav@559	1217	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	1218	/*
jaroslav@559	1219	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	1220	* These values are inexpensive approximations of the first and
jaroslav@559	1221	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	1222	*/
jaroslav@559	1223	short pivot1 = a[e2];
jaroslav@559	1224	short pivot2 = a[e4];
jaroslav@559	1225
jaroslav@559	1226	/*
jaroslav@559	1227	* The first and the last elements to be sorted are moved to the
jaroslav@559	1228	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	1229	* is complete, the pivots are swapped back into their final
jaroslav@559	1230	* positions, and excluded from subsequent sorting.
jaroslav@559	1231	*/
jaroslav@559	1232	a[e2] = a[left];
jaroslav@559	1233	a[e4] = a[right];
jaroslav@559	1234
jaroslav@559	1235	/*
jaroslav@559	1236	* Skip elements, which are less or greater than pivot values.
jaroslav@559	1237	*/
jaroslav@559	1238	while (a[++less] < pivot1);
jaroslav@559	1239	while (a[--great] > pivot2);
jaroslav@559	1240
jaroslav@559	1241	/*
jaroslav@559	1242	* Partitioning:
jaroslav@559	1243	*
jaroslav@559	1244	* left part center part right part
jaroslav@559	1245	* +--------------------------------------------------------------+
jaroslav@559	1246	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	1247	* +--------------------------------------------------------------+
jaroslav@559	1248	* ^ ^ ^
jaroslav@559	1249	* \| \| \|
jaroslav@559	1250	* less k great
jaroslav@559	1251	*
jaroslav@559	1252	* Invariants:
jaroslav@559	1253	*
jaroslav@559	1254	* all in (left, less) < pivot1
jaroslav@559	1255	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	1256	* all in (great, right) > pivot2
jaroslav@559	1257	*
jaroslav@559	1258	* Pointer k is the first index of ?-part.
jaroslav@559	1259	*/
jaroslav@559	1260	outer:
jaroslav@559	1261	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	1262	short ak = a[k];
jaroslav@559	1263	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	1264	a[k] = a[less];
jaroslav@559	1265	/*
jaroslav@559	1266	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	1267	* of "a[i++] = b;" due to performance issue.
jaroslav@559	1268	*/
jaroslav@559	1269	a[less] = ak;
jaroslav@559	1270	++less;
jaroslav@559	1271	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	1272	while (a[great] > pivot2) {
jaroslav@559	1273	if (great-- == k) {
jaroslav@559	1274	break outer;
jaroslav@559	1275	}
jaroslav@559	1276	}
jaroslav@559	1277	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	1278	a[k] = a[less];
jaroslav@559	1279	a[less] = a[great];
jaroslav@559	1280	++less;
jaroslav@559	1281	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	1282	a[k] = a[great];
jaroslav@559	1283	}
jaroslav@559	1284	/*
jaroslav@559	1285	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	1286	* of "a[i--] = b;" due to performance issue.
jaroslav@559	1287	*/
jaroslav@559	1288	a[great] = ak;
jaroslav@559	1289	--great;
jaroslav@559	1290	}
jaroslav@559	1291	}
jaroslav@559	1292
jaroslav@559	1293	// Swap pivots into their final positions
jaroslav@559	1294	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	1295	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	1296
jaroslav@559	1297	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	1298	sort(a, left, less - 2, leftmost);
jaroslav@559	1299	sort(a, great + 2, right, false);
jaroslav@559	1300
jaroslav@559	1301	/*
jaroslav@559	1302	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	1303	* swap internal pivot values to ends.
jaroslav@559	1304	*/
jaroslav@559	1305	if (less < e1 && e5 < great) {
jaroslav@559	1306	/*
jaroslav@559	1307	* Skip elements, which are equal to pivot values.
jaroslav@559	1308	*/
jaroslav@559	1309	while (a[less] == pivot1) {
jaroslav@559	1310	++less;
jaroslav@559	1311	}
jaroslav@559	1312
jaroslav@559	1313	while (a[great] == pivot2) {
jaroslav@559	1314	--great;
jaroslav@559	1315	}
jaroslav@559	1316
jaroslav@559	1317	/*
jaroslav@559	1318	* Partitioning:
jaroslav@559	1319	*
jaroslav@559	1320	* left part center part right part
jaroslav@559	1321	* +----------------------------------------------------------+
jaroslav@559	1322	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	1323	* +----------------------------------------------------------+
jaroslav@559	1324	* ^ ^ ^
jaroslav@559	1325	* \| \| \|
jaroslav@559	1326	* less k great
jaroslav@559	1327	*
jaroslav@559	1328	* Invariants:
jaroslav@559	1329	*
jaroslav@559	1330	* all in (*, less) == pivot1
jaroslav@559	1331	* pivot1 < all in [less, k) < pivot2
jaroslav@559	1332	* all in (great, *) == pivot2
jaroslav@559	1333	*
jaroslav@559	1334	* Pointer k is the first index of ?-part.
jaroslav@559	1335	*/
jaroslav@559	1336	outer:
jaroslav@559	1337	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	1338	short ak = a[k];
jaroslav@559	1339	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	1340	a[k] = a[less];
jaroslav@559	1341	a[less] = ak;
jaroslav@559	1342	++less;
jaroslav@559	1343	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	1344	while (a[great] == pivot2) {
jaroslav@559	1345	if (great-- == k) {
jaroslav@559	1346	break outer;
jaroslav@559	1347	}
jaroslav@559	1348	}
jaroslav@559	1349	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	1350	a[k] = a[less];
jaroslav@559	1351	/*
jaroslav@559	1352	* Even though a[great] equals to pivot1, the
jaroslav@559	1353	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	1354	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	1355	* of different signs. Therefore in float and
jaroslav@559	1356	* double sorting methods we have to use more
jaroslav@559	1357	* accurate assignment a[less] = a[great].
jaroslav@559	1358	*/
jaroslav@559	1359	a[less] = pivot1;
jaroslav@559	1360	++less;
jaroslav@559	1361	} else { // pivot1 < a[great] < pivot2
jaroslav@559	1362	a[k] = a[great];
jaroslav@559	1363	}
jaroslav@559	1364	a[great] = ak;
jaroslav@559	1365	--great;
jaroslav@559	1366	}
jaroslav@559	1367	}
jaroslav@559	1368	}
jaroslav@559	1369
jaroslav@559	1370	// Sort center part recursively
jaroslav@559	1371	sort(a, less, great, false);
jaroslav@559	1372
jaroslav@559	1373	} else { // Partitioning with one pivot
jaroslav@559	1374	/*
jaroslav@559	1375	* Use the third of the five sorted elements as pivot.
jaroslav@559	1376	* This value is inexpensive approximation of the median.
jaroslav@559	1377	*/
jaroslav@559	1378	short pivot = a[e3];
jaroslav@559	1379
jaroslav@559	1380	/*
jaroslav@559	1381	* Partitioning degenerates to the traditional 3-way
jaroslav@559	1382	* (or "Dutch National Flag") schema:
jaroslav@559	1383	*
jaroslav@559	1384	* left part center part right part
jaroslav@559	1385	* +-------------------------------------------------+
jaroslav@559	1386	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	1387	* +-------------------------------------------------+
jaroslav@559	1388	* ^ ^ ^
jaroslav@559	1389	* \| \| \|
jaroslav@559	1390	* less k great
jaroslav@559	1391	*
jaroslav@559	1392	* Invariants:
jaroslav@559	1393	*
jaroslav@559	1394	* all in (left, less) < pivot
jaroslav@559	1395	* all in [less, k) == pivot
jaroslav@559	1396	* all in (great, right) > pivot
jaroslav@559	1397	*
jaroslav@559	1398	* Pointer k is the first index of ?-part.
jaroslav@559	1399	*/
jaroslav@559	1400	for (int k = less; k <= great; ++k) {
jaroslav@559	1401	if (a[k] == pivot) {
jaroslav@559	1402	continue;
jaroslav@559	1403	}
jaroslav@559	1404	short ak = a[k];
jaroslav@559	1405	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	1406	a[k] = a[less];
jaroslav@559	1407	a[less] = ak;
jaroslav@559	1408	++less;
jaroslav@559	1409	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	1410	while (a[great] > pivot) {
jaroslav@559	1411	--great;
jaroslav@559	1412	}
jaroslav@559	1413	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	1414	a[k] = a[less];
jaroslav@559	1415	a[less] = a[great];
jaroslav@559	1416	++less;
jaroslav@559	1417	} else { // a[great] == pivot
jaroslav@559	1418	/*
jaroslav@559	1419	* Even though a[great] equals to pivot, the
jaroslav@559	1420	* assignment a[k] = pivot may be incorrect,
jaroslav@559	1421	* if a[great] and pivot are floating-point
jaroslav@559	1422	* zeros of different signs. Therefore in float
jaroslav@559	1423	* and double sorting methods we have to use
jaroslav@559	1424	* more accurate assignment a[k] = a[great].
jaroslav@559	1425	*/
jaroslav@559	1426	a[k] = pivot;
jaroslav@559	1427	}
jaroslav@559	1428	a[great] = ak;
jaroslav@559	1429	--great;
jaroslav@559	1430	}
jaroslav@559	1431	}
jaroslav@559	1432
jaroslav@559	1433	/*
jaroslav@559	1434	* Sort left and right parts recursively.
jaroslav@559	1435	* All elements from center part are equal
jaroslav@559	1436	* and, therefore, already sorted.
jaroslav@559	1437	*/
jaroslav@559	1438	sort(a, left, less - 1, leftmost);
jaroslav@559	1439	sort(a, great + 1, right, false);
jaroslav@559	1440	}
jaroslav@559	1441	}
jaroslav@559	1442
jaroslav@559	1443	/**
jaroslav@559	1444	* Sorts the specified array.
jaroslav@559	1445	*
jaroslav@559	1446	* @param a the array to be sorted
jaroslav@559	1447	*/
jaroslav@559	1448	public static void sort(char[] a) {
jaroslav@559	1449	sort(a, 0, a.length - 1);
jaroslav@559	1450	}
jaroslav@559	1451
jaroslav@559	1452	/**
jaroslav@559	1453	* Sorts the specified range of the array.
jaroslav@559	1454	*
jaroslav@559	1455	* @param a the array to be sorted
jaroslav@559	1456	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1457	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1458	*/
jaroslav@559	1459	public static void sort(char[] a, int left, int right) {
jaroslav@559	1460	// Use counting sort on large arrays
jaroslav@559	1461	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
jaroslav@559	1462	int[] count = new int[NUM_CHAR_VALUES];
jaroslav@559	1463
jaroslav@559	1464	for (int i = left - 1; ++i <= right;
jaroslav@559	1465	count[a[i]]++
jaroslav@559	1466	);
jaroslav@559	1467	for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
jaroslav@559	1468	while (count[--i] == 0);
jaroslav@559	1469	char value = (char) i;
jaroslav@559	1470	int s = count[i];
jaroslav@559	1471
jaroslav@559	1472	do {
jaroslav@559	1473	a[--k] = value;
jaroslav@559	1474	} while (--s > 0);
jaroslav@559	1475	}
jaroslav@559	1476	} else { // Use Dual-Pivot Quicksort on small arrays
jaroslav@559	1477	doSort(a, left, right);
jaroslav@559	1478	}
jaroslav@559	1479	}
jaroslav@559	1480
jaroslav@559	1481	/** The number of distinct char values. */
jaroslav@559	1482	private static final int NUM_CHAR_VALUES = 1 << 16;
jaroslav@559	1483
jaroslav@559	1484	/**
jaroslav@559	1485	* Sorts the specified range of the array.
jaroslav@559	1486	*
jaroslav@559	1487	* @param a the array to be sorted
jaroslav@559	1488	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1489	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1490	*/
jaroslav@559	1491	private static void doSort(char[] a, int left, int right) {
jaroslav@559	1492	// Use Quicksort on small arrays
jaroslav@559	1493	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	1494	sort(a, left, right, true);
jaroslav@559	1495	return;
jaroslav@559	1496	}
jaroslav@559	1497
jaroslav@559	1498	/*
jaroslav@559	1499	* Index run[i] is the start of i-th run
jaroslav@559	1500	* (ascending or descending sequence).
jaroslav@559	1501	*/
jaroslav@559	1502	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	1503	int count = 0; run[0] = left;
jaroslav@559	1504
jaroslav@559	1505	// Check if the array is nearly sorted
jaroslav@559	1506	for (int k = left; k < right; run[count] = k) {
jaroslav@559	1507	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	1508	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	1509	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	1510	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	1511	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	1512	char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	1513	}
jaroslav@559	1514	} else { // equal
jaroslav@559	1515	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	1516	if (--m == 0) {
jaroslav@559	1517	sort(a, left, right, true);
jaroslav@559	1518	return;
jaroslav@559	1519	}
jaroslav@559	1520	}
jaroslav@559	1521	}
jaroslav@559	1522
jaroslav@559	1523	/*
jaroslav@559	1524	* The array is not highly structured,
jaroslav@559	1525	* use Quicksort instead of merge sort.
jaroslav@559	1526	*/
jaroslav@559	1527	if (++count == MAX_RUN_COUNT) {
jaroslav@559	1528	sort(a, left, right, true);
jaroslav@559	1529	return;
jaroslav@559	1530	}
jaroslav@559	1531	}
jaroslav@559	1532
jaroslav@559	1533	// Check special cases
jaroslav@559	1534	if (run[count] == right++) { // The last run contains one element
jaroslav@559	1535	run[++count] = right;
jaroslav@559	1536	} else if (count == 1) { // The array is already sorted
jaroslav@559	1537	return;
jaroslav@559	1538	}
jaroslav@559	1539
jaroslav@559	1540	/*
jaroslav@559	1541	* Create temporary array, which is used for merging.
jaroslav@559	1542	* Implementation note: variable "right" is increased by 1.
jaroslav@559	1543	*/
jaroslav@559	1544	char[] b; byte odd = 0;
jaroslav@559	1545	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	1546
jaroslav@559	1547	if (odd == 0) {
jaroslav@559	1548	b = a; a = new char[b.length];
jaroslav@559	1549	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	1550	} else {
jaroslav@559	1551	b = new char[a.length];
jaroslav@559	1552	}
jaroslav@559	1553
jaroslav@559	1554	// Merging
jaroslav@559	1555	for (int last; count > 1; count = last) {
jaroslav@559	1556	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	1557	int hi = run[k], mi = run[k - 1];
jaroslav@559	1558	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	1559	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	1560	b[i] = a[p++];
jaroslav@559	1561	} else {
jaroslav@559	1562	b[i] = a[q++];
jaroslav@559	1563	}
jaroslav@559	1564	}
jaroslav@559	1565	run[++last] = hi;
jaroslav@559	1566	}
jaroslav@559	1567	if ((count & 1) != 0) {
jaroslav@559	1568	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	1569	b[i] = a[i]
jaroslav@559	1570	);
jaroslav@559	1571	run[++last] = right;
jaroslav@559	1572	}
jaroslav@559	1573	char[] t = a; a = b; b = t;
jaroslav@559	1574	}
jaroslav@559	1575	}
jaroslav@559	1576
jaroslav@559	1577	/**
jaroslav@559	1578	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	1579	*
jaroslav@559	1580	* @param a the array to be sorted
jaroslav@559	1581	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1582	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1583	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	1584	*/
jaroslav@559	1585	private static void sort(char[] a, int left, int right, boolean leftmost) {
jaroslav@559	1586	int length = right - left + 1;
jaroslav@559	1587
jaroslav@559	1588	// Use insertion sort on tiny arrays
jaroslav@559	1589	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	1590	if (leftmost) {
jaroslav@559	1591	/*
jaroslav@559	1592	* Traditional (without sentinel) insertion sort,
jaroslav@559	1593	* optimized for server VM, is used in case of
jaroslav@559	1594	* the leftmost part.
jaroslav@559	1595	*/
jaroslav@559	1596	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	1597	char ai = a[i + 1];
jaroslav@559	1598	while (ai < a[j]) {
jaroslav@559	1599	a[j + 1] = a[j];
jaroslav@559	1600	if (j-- == left) {
jaroslav@559	1601	break;
jaroslav@559	1602	}
jaroslav@559	1603	}
jaroslav@559	1604	a[j + 1] = ai;
jaroslav@559	1605	}
jaroslav@559	1606	} else {
jaroslav@559	1607	/*
jaroslav@559	1608	* Skip the longest ascending sequence.
jaroslav@559	1609	*/
jaroslav@559	1610	do {
jaroslav@559	1611	if (left >= right) {
jaroslav@559	1612	return;
jaroslav@559	1613	}
jaroslav@559	1614	} while (a[++left] >= a[left - 1]);
jaroslav@559	1615
jaroslav@559	1616	/*
jaroslav@559	1617	* Every element from adjoining part plays the role
jaroslav@559	1618	* of sentinel, therefore this allows us to avoid the
jaroslav@559	1619	* left range check on each iteration. Moreover, we use
jaroslav@559	1620	* the more optimized algorithm, so called pair insertion
jaroslav@559	1621	* sort, which is faster (in the context of Quicksort)
jaroslav@559	1622	* than traditional implementation of insertion sort.
jaroslav@559	1623	*/
jaroslav@559	1624	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	1625	char a1 = a[k], a2 = a[left];
jaroslav@559	1626
jaroslav@559	1627	if (a1 < a2) {
jaroslav@559	1628	a2 = a1; a1 = a[left];
jaroslav@559	1629	}
jaroslav@559	1630	while (a1 < a[--k]) {
jaroslav@559	1631	a[k + 2] = a[k];
jaroslav@559	1632	}
jaroslav@559	1633	a[++k + 1] = a1;
jaroslav@559	1634
jaroslav@559	1635	while (a2 < a[--k]) {
jaroslav@559	1636	a[k + 1] = a[k];
jaroslav@559	1637	}
jaroslav@559	1638	a[k + 1] = a2;
jaroslav@559	1639	}
jaroslav@559	1640	char last = a[right];
jaroslav@559	1641
jaroslav@559	1642	while (last < a[--right]) {
jaroslav@559	1643	a[right + 1] = a[right];
jaroslav@559	1644	}
jaroslav@559	1645	a[right + 1] = last;
jaroslav@559	1646	}
jaroslav@559	1647	return;
jaroslav@559	1648	}
jaroslav@559	1649
jaroslav@559	1650	// Inexpensive approximation of length / 7
jaroslav@559	1651	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	1652
jaroslav@559	1653	/*
jaroslav@559	1654	* Sort five evenly spaced elements around (and including) the
jaroslav@559	1655	* center element in the range. These elements will be used for
jaroslav@559	1656	* pivot selection as described below. The choice for spacing
jaroslav@559	1657	* these elements was empirically determined to work well on
jaroslav@559	1658	* a wide variety of inputs.
jaroslav@559	1659	*/
jaroslav@559	1660	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	1661	int e2 = e3 - seventh;
jaroslav@559	1662	int e1 = e2 - seventh;
jaroslav@559	1663	int e4 = e3 + seventh;
jaroslav@559	1664	int e5 = e4 + seventh;
jaroslav@559	1665
jaroslav@559	1666	// Sort these elements using insertion sort
jaroslav@559	1667	if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1668
jaroslav@559	1669	if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1670	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1671	}
jaroslav@559	1672	if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	1673	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1674	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1675	}
jaroslav@559	1676	}
jaroslav@559	1677	if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	1678	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	1679	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	1680	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	1681	}
jaroslav@559	1682	}
jaroslav@559	1683	}
jaroslav@559	1684
jaroslav@559	1685	// Pointers
jaroslav@559	1686	int less = left; // The index of the first element of center part
jaroslav@559	1687	int great = right; // The index before the first element of right part
jaroslav@559	1688
jaroslav@559	1689	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	1690	/*
jaroslav@559	1691	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	1692	* These values are inexpensive approximations of the first and
jaroslav@559	1693	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	1694	*/
jaroslav@559	1695	char pivot1 = a[e2];
jaroslav@559	1696	char pivot2 = a[e4];
jaroslav@559	1697
jaroslav@559	1698	/*
jaroslav@559	1699	* The first and the last elements to be sorted are moved to the
jaroslav@559	1700	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	1701	* is complete, the pivots are swapped back into their final
jaroslav@559	1702	* positions, and excluded from subsequent sorting.
jaroslav@559	1703	*/
jaroslav@559	1704	a[e2] = a[left];
jaroslav@559	1705	a[e4] = a[right];
jaroslav@559	1706
jaroslav@559	1707	/*
jaroslav@559	1708	* Skip elements, which are less or greater than pivot values.
jaroslav@559	1709	*/
jaroslav@559	1710	while (a[++less] < pivot1);
jaroslav@559	1711	while (a[--great] > pivot2);
jaroslav@559	1712
jaroslav@559	1713	/*
jaroslav@559	1714	* Partitioning:
jaroslav@559	1715	*
jaroslav@559	1716	* left part center part right part
jaroslav@559	1717	* +--------------------------------------------------------------+
jaroslav@559	1718	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	1719	* +--------------------------------------------------------------+
jaroslav@559	1720	* ^ ^ ^
jaroslav@559	1721	* \| \| \|
jaroslav@559	1722	* less k great
jaroslav@559	1723	*
jaroslav@559	1724	* Invariants:
jaroslav@559	1725	*
jaroslav@559	1726	* all in (left, less) < pivot1
jaroslav@559	1727	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	1728	* all in (great, right) > pivot2
jaroslav@559	1729	*
jaroslav@559	1730	* Pointer k is the first index of ?-part.
jaroslav@559	1731	*/
jaroslav@559	1732	outer:
jaroslav@559	1733	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	1734	char ak = a[k];
jaroslav@559	1735	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	1736	a[k] = a[less];
jaroslav@559	1737	/*
jaroslav@559	1738	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	1739	* of "a[i++] = b;" due to performance issue.
jaroslav@559	1740	*/
jaroslav@559	1741	a[less] = ak;
jaroslav@559	1742	++less;
jaroslav@559	1743	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	1744	while (a[great] > pivot2) {
jaroslav@559	1745	if (great-- == k) {
jaroslav@559	1746	break outer;
jaroslav@559	1747	}
jaroslav@559	1748	}
jaroslav@559	1749	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	1750	a[k] = a[less];
jaroslav@559	1751	a[less] = a[great];
jaroslav@559	1752	++less;
jaroslav@559	1753	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	1754	a[k] = a[great];
jaroslav@559	1755	}
jaroslav@559	1756	/*
jaroslav@559	1757	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	1758	* of "a[i--] = b;" due to performance issue.
jaroslav@559	1759	*/
jaroslav@559	1760	a[great] = ak;
jaroslav@559	1761	--great;
jaroslav@559	1762	}
jaroslav@559	1763	}
jaroslav@559	1764
jaroslav@559	1765	// Swap pivots into their final positions
jaroslav@559	1766	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	1767	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	1768
jaroslav@559	1769	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	1770	sort(a, left, less - 2, leftmost);
jaroslav@559	1771	sort(a, great + 2, right, false);
jaroslav@559	1772
jaroslav@559	1773	/*
jaroslav@559	1774	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	1775	* swap internal pivot values to ends.
jaroslav@559	1776	*/
jaroslav@559	1777	if (less < e1 && e5 < great) {
jaroslav@559	1778	/*
jaroslav@559	1779	* Skip elements, which are equal to pivot values.
jaroslav@559	1780	*/
jaroslav@559	1781	while (a[less] == pivot1) {
jaroslav@559	1782	++less;
jaroslav@559	1783	}
jaroslav@559	1784
jaroslav@559	1785	while (a[great] == pivot2) {
jaroslav@559	1786	--great;
jaroslav@559	1787	}
jaroslav@559	1788
jaroslav@559	1789	/*
jaroslav@559	1790	* Partitioning:
jaroslav@559	1791	*
jaroslav@559	1792	* left part center part right part
jaroslav@559	1793	* +----------------------------------------------------------+
jaroslav@559	1794	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	1795	* +----------------------------------------------------------+
jaroslav@559	1796	* ^ ^ ^
jaroslav@559	1797	* \| \| \|
jaroslav@559	1798	* less k great
jaroslav@559	1799	*
jaroslav@559	1800	* Invariants:
jaroslav@559	1801	*
jaroslav@559	1802	* all in (*, less) == pivot1
jaroslav@559	1803	* pivot1 < all in [less, k) < pivot2
jaroslav@559	1804	* all in (great, *) == pivot2
jaroslav@559	1805	*
jaroslav@559	1806	* Pointer k is the first index of ?-part.
jaroslav@559	1807	*/
jaroslav@559	1808	outer:
jaroslav@559	1809	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	1810	char ak = a[k];
jaroslav@559	1811	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	1812	a[k] = a[less];
jaroslav@559	1813	a[less] = ak;
jaroslav@559	1814	++less;
jaroslav@559	1815	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	1816	while (a[great] == pivot2) {
jaroslav@559	1817	if (great-- == k) {
jaroslav@559	1818	break outer;
jaroslav@559	1819	}
jaroslav@559	1820	}
jaroslav@559	1821	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	1822	a[k] = a[less];
jaroslav@559	1823	/*
jaroslav@559	1824	* Even though a[great] equals to pivot1, the
jaroslav@559	1825	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	1826	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	1827	* of different signs. Therefore in float and
jaroslav@559	1828	* double sorting methods we have to use more
jaroslav@559	1829	* accurate assignment a[less] = a[great].
jaroslav@559	1830	*/
jaroslav@559	1831	a[less] = pivot1;
jaroslav@559	1832	++less;
jaroslav@559	1833	} else { // pivot1 < a[great] < pivot2
jaroslav@559	1834	a[k] = a[great];
jaroslav@559	1835	}
jaroslav@559	1836	a[great] = ak;
jaroslav@559	1837	--great;
jaroslav@559	1838	}
jaroslav@559	1839	}
jaroslav@559	1840	}
jaroslav@559	1841
jaroslav@559	1842	// Sort center part recursively
jaroslav@559	1843	sort(a, less, great, false);
jaroslav@559	1844
jaroslav@559	1845	} else { // Partitioning with one pivot
jaroslav@559	1846	/*
jaroslav@559	1847	* Use the third of the five sorted elements as pivot.
jaroslav@559	1848	* This value is inexpensive approximation of the median.
jaroslav@559	1849	*/
jaroslav@559	1850	char pivot = a[e3];
jaroslav@559	1851
jaroslav@559	1852	/*
jaroslav@559	1853	* Partitioning degenerates to the traditional 3-way
jaroslav@559	1854	* (or "Dutch National Flag") schema:
jaroslav@559	1855	*
jaroslav@559	1856	* left part center part right part
jaroslav@559	1857	* +-------------------------------------------------+
jaroslav@559	1858	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	1859	* +-------------------------------------------------+
jaroslav@559	1860	* ^ ^ ^
jaroslav@559	1861	* \| \| \|
jaroslav@559	1862	* less k great
jaroslav@559	1863	*
jaroslav@559	1864	* Invariants:
jaroslav@559	1865	*
jaroslav@559	1866	* all in (left, less) < pivot
jaroslav@559	1867	* all in [less, k) == pivot
jaroslav@559	1868	* all in (great, right) > pivot
jaroslav@559	1869	*
jaroslav@559	1870	* Pointer k is the first index of ?-part.
jaroslav@559	1871	*/
jaroslav@559	1872	for (int k = less; k <= great; ++k) {
jaroslav@559	1873	if (a[k] == pivot) {
jaroslav@559	1874	continue;
jaroslav@559	1875	}
jaroslav@559	1876	char ak = a[k];
jaroslav@559	1877	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	1878	a[k] = a[less];
jaroslav@559	1879	a[less] = ak;
jaroslav@559	1880	++less;
jaroslav@559	1881	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	1882	while (a[great] > pivot) {
jaroslav@559	1883	--great;
jaroslav@559	1884	}
jaroslav@559	1885	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	1886	a[k] = a[less];
jaroslav@559	1887	a[less] = a[great];
jaroslav@559	1888	++less;
jaroslav@559	1889	} else { // a[great] == pivot
jaroslav@559	1890	/*
jaroslav@559	1891	* Even though a[great] equals to pivot, the
jaroslav@559	1892	* assignment a[k] = pivot may be incorrect,
jaroslav@559	1893	* if a[great] and pivot are floating-point
jaroslav@559	1894	* zeros of different signs. Therefore in float
jaroslav@559	1895	* and double sorting methods we have to use
jaroslav@559	1896	* more accurate assignment a[k] = a[great].
jaroslav@559	1897	*/
jaroslav@559	1898	a[k] = pivot;
jaroslav@559	1899	}
jaroslav@559	1900	a[great] = ak;
jaroslav@559	1901	--great;
jaroslav@559	1902	}
jaroslav@559	1903	}
jaroslav@559	1904
jaroslav@559	1905	/*
jaroslav@559	1906	* Sort left and right parts recursively.
jaroslav@559	1907	* All elements from center part are equal
jaroslav@559	1908	* and, therefore, already sorted.
jaroslav@559	1909	*/
jaroslav@559	1910	sort(a, left, less - 1, leftmost);
jaroslav@559	1911	sort(a, great + 1, right, false);
jaroslav@559	1912	}
jaroslav@559	1913	}
jaroslav@559	1914
jaroslav@559	1915	/** The number of distinct byte values. */
jaroslav@559	1916	private static final int NUM_BYTE_VALUES = 1 << 8;
jaroslav@559	1917
jaroslav@559	1918	/**
jaroslav@559	1919	* Sorts the specified array.
jaroslav@559	1920	*
jaroslav@559	1921	* @param a the array to be sorted
jaroslav@559	1922	*/
jaroslav@559	1923	public static void sort(byte[] a) {
jaroslav@559	1924	sort(a, 0, a.length - 1);
jaroslav@559	1925	}
jaroslav@559	1926
jaroslav@559	1927	/**
jaroslav@559	1928	* Sorts the specified range of the array.
jaroslav@559	1929	*
jaroslav@559	1930	* @param a the array to be sorted
jaroslav@559	1931	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1932	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1933	*/
jaroslav@559	1934	public static void sort(byte[] a, int left, int right) {
jaroslav@559	1935	// Use counting sort on large arrays
jaroslav@559	1936	if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
jaroslav@559	1937	int[] count = new int[NUM_BYTE_VALUES];
jaroslav@559	1938
jaroslav@559	1939	for (int i = left - 1; ++i <= right;
jaroslav@559	1940	count[a[i] - Byte.MIN_VALUE]++
jaroslav@559	1941	);
jaroslav@559	1942	for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
jaroslav@559	1943	while (count[--i] == 0);
jaroslav@559	1944	byte value = (byte) (i + Byte.MIN_VALUE);
jaroslav@559	1945	int s = count[i];
jaroslav@559	1946
jaroslav@559	1947	do {
jaroslav@559	1948	a[--k] = value;
jaroslav@559	1949	} while (--s > 0);
jaroslav@559	1950	}
jaroslav@559	1951	} else { // Use insertion sort on small arrays
jaroslav@559	1952	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	1953	byte ai = a[i + 1];
jaroslav@559	1954	while (ai < a[j]) {
jaroslav@559	1955	a[j + 1] = a[j];
jaroslav@559	1956	if (j-- == left) {
jaroslav@559	1957	break;
jaroslav@559	1958	}
jaroslav@559	1959	}
jaroslav@559	1960	a[j + 1] = ai;
jaroslav@559	1961	}
jaroslav@559	1962	}
jaroslav@559	1963	}
jaroslav@559	1964
jaroslav@559	1965	/**
jaroslav@559	1966	* Sorts the specified array.
jaroslav@559	1967	*
jaroslav@559	1968	* @param a the array to be sorted
jaroslav@559	1969	*/
jaroslav@559	1970	public static void sort(float[] a) {
jaroslav@559	1971	sort(a, 0, a.length - 1);
jaroslav@559	1972	}
jaroslav@559	1973
jaroslav@559	1974	/**
jaroslav@559	1975	* Sorts the specified range of the array.
jaroslav@559	1976	*
jaroslav@559	1977	* @param a the array to be sorted
jaroslav@559	1978	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	1979	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	1980	*/
jaroslav@559	1981	public static void sort(float[] a, int left, int right) {
jaroslav@559	1982	/*
jaroslav@559	1983	* Phase 1: Move NaNs to the end of the array.
jaroslav@559	1984	*/
jaroslav@559	1985	while (left <= right && Float.isNaN(a[right])) {
jaroslav@559	1986	--right;
jaroslav@559	1987	}
jaroslav@559	1988	for (int k = right; --k >= left; ) {
jaroslav@559	1989	float ak = a[k];
jaroslav@559	1990	if (ak != ak) { // a[k] is NaN
jaroslav@559	1991	a[k] = a[right];
jaroslav@559	1992	a[right] = ak;
jaroslav@559	1993	--right;
jaroslav@559	1994	}
jaroslav@559	1995	}
jaroslav@559	1996
jaroslav@559	1997	/*
jaroslav@559	1998	* Phase 2: Sort everything except NaNs (which are already in place).
jaroslav@559	1999	*/
jaroslav@559	2000	doSort(a, left, right);
jaroslav@559	2001
jaroslav@559	2002	/*
jaroslav@559	2003	* Phase 3: Place negative zeros before positive zeros.
jaroslav@559	2004	*/
jaroslav@559	2005	int hi = right;
jaroslav@559	2006
jaroslav@559	2007	/*
jaroslav@559	2008	* Find the first zero, or first positive, or last negative element.
jaroslav@559	2009	*/
jaroslav@559	2010	while (left < hi) {
jaroslav@559	2011	int middle = (left + hi) >>> 1;
jaroslav@559	2012	float middleValue = a[middle];
jaroslav@559	2013
jaroslav@559	2014	if (middleValue < 0.0f) {
jaroslav@559	2015	left = middle + 1;
jaroslav@559	2016	} else {
jaroslav@559	2017	hi = middle;
jaroslav@559	2018	}
jaroslav@559	2019	}
jaroslav@559	2020
jaroslav@559	2021	/*
jaroslav@559	2022	* Skip the last negative value (if any) or all leading negative zeros.
jaroslav@559	2023	*/
jaroslav@559	2024	while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
jaroslav@559	2025	++left;
jaroslav@559	2026	}
jaroslav@559	2027
jaroslav@559	2028	/*
jaroslav@559	2029	* Move negative zeros to the beginning of the sub-range.
jaroslav@559	2030	*
jaroslav@559	2031	* Partitioning:
jaroslav@559	2032	*
jaroslav@559	2033	* +----------------------------------------------------+
jaroslav@559	2034	* \| < 0.0 \| -0.0 \| 0.0 \| ? ( >= 0.0 ) \|
jaroslav@559	2035	* +----------------------------------------------------+
jaroslav@559	2036	* ^ ^ ^
jaroslav@559	2037	* \| \| \|
jaroslav@559	2038	* left p k
jaroslav@559	2039	*
jaroslav@559	2040	* Invariants:
jaroslav@559	2041	*
jaroslav@559	2042	* all in (*, left) < 0.0
jaroslav@559	2043	* all in [left, p) == -0.0
jaroslav@559	2044	* all in [p, k) == 0.0
jaroslav@559	2045	* all in [k, right] >= 0.0
jaroslav@559	2046	*
jaroslav@559	2047	* Pointer k is the first index of ?-part.
jaroslav@559	2048	*/
jaroslav@559	2049	for (int k = left, p = left - 1; ++k <= right; ) {
jaroslav@559	2050	float ak = a[k];
jaroslav@559	2051	if (ak != 0.0f) {
jaroslav@559	2052	break;
jaroslav@559	2053	}
jaroslav@559	2054	if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
jaroslav@559	2055	a[k] = 0.0f;
jaroslav@559	2056	a[++p] = -0.0f;
jaroslav@559	2057	}
jaroslav@559	2058	}
jaroslav@559	2059	}
jaroslav@559	2060
jaroslav@559	2061	/**
jaroslav@559	2062	* Sorts the specified range of the array.
jaroslav@559	2063	*
jaroslav@559	2064	* @param a the array to be sorted
jaroslav@559	2065	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	2066	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	2067	*/
jaroslav@559	2068	private static void doSort(float[] a, int left, int right) {
jaroslav@559	2069	// Use Quicksort on small arrays
jaroslav@559	2070	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	2071	sort(a, left, right, true);
jaroslav@559	2072	return;
jaroslav@559	2073	}
jaroslav@559	2074
jaroslav@559	2075	/*
jaroslav@559	2076	* Index run[i] is the start of i-th run
jaroslav@559	2077	* (ascending or descending sequence).
jaroslav@559	2078	*/
jaroslav@559	2079	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	2080	int count = 0; run[0] = left;
jaroslav@559	2081
jaroslav@559	2082	// Check if the array is nearly sorted
jaroslav@559	2083	for (int k = left; k < right; run[count] = k) {
jaroslav@559	2084	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	2085	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	2086	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	2087	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	2088	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	2089	float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	2090	}
jaroslav@559	2091	} else { // equal
jaroslav@559	2092	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	2093	if (--m == 0) {
jaroslav@559	2094	sort(a, left, right, true);
jaroslav@559	2095	return;
jaroslav@559	2096	}
jaroslav@559	2097	}
jaroslav@559	2098	}
jaroslav@559	2099
jaroslav@559	2100	/*
jaroslav@559	2101	* The array is not highly structured,
jaroslav@559	2102	* use Quicksort instead of merge sort.
jaroslav@559	2103	*/
jaroslav@559	2104	if (++count == MAX_RUN_COUNT) {
jaroslav@559	2105	sort(a, left, right, true);
jaroslav@559	2106	return;
jaroslav@559	2107	}
jaroslav@559	2108	}
jaroslav@559	2109
jaroslav@559	2110	// Check special cases
jaroslav@559	2111	if (run[count] == right++) { // The last run contains one element
jaroslav@559	2112	run[++count] = right;
jaroslav@559	2113	} else if (count == 1) { // The array is already sorted
jaroslav@559	2114	return;
jaroslav@559	2115	}
jaroslav@559	2116
jaroslav@559	2117	/*
jaroslav@559	2118	* Create temporary array, which is used for merging.
jaroslav@559	2119	* Implementation note: variable "right" is increased by 1.
jaroslav@559	2120	*/
jaroslav@559	2121	float[] b; byte odd = 0;
jaroslav@559	2122	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	2123
jaroslav@559	2124	if (odd == 0) {
jaroslav@559	2125	b = a; a = new float[b.length];
jaroslav@559	2126	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	2127	} else {
jaroslav@559	2128	b = new float[a.length];
jaroslav@559	2129	}
jaroslav@559	2130
jaroslav@559	2131	// Merging
jaroslav@559	2132	for (int last; count > 1; count = last) {
jaroslav@559	2133	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	2134	int hi = run[k], mi = run[k - 1];
jaroslav@559	2135	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	2136	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	2137	b[i] = a[p++];
jaroslav@559	2138	} else {
jaroslav@559	2139	b[i] = a[q++];
jaroslav@559	2140	}
jaroslav@559	2141	}
jaroslav@559	2142	run[++last] = hi;
jaroslav@559	2143	}
jaroslav@559	2144	if ((count & 1) != 0) {
jaroslav@559	2145	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	2146	b[i] = a[i]
jaroslav@559	2147	);
jaroslav@559	2148	run[++last] = right;
jaroslav@559	2149	}
jaroslav@559	2150	float[] t = a; a = b; b = t;
jaroslav@559	2151	}
jaroslav@559	2152	}
jaroslav@559	2153
jaroslav@559	2154	/**
jaroslav@559	2155	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	2156	*
jaroslav@559	2157	* @param a the array to be sorted
jaroslav@559	2158	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	2159	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	2160	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	2161	*/
jaroslav@559	2162	private static void sort(float[] a, int left, int right, boolean leftmost) {
jaroslav@559	2163	int length = right - left + 1;
jaroslav@559	2164
jaroslav@559	2165	// Use insertion sort on tiny arrays
jaroslav@559	2166	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	2167	if (leftmost) {
jaroslav@559	2168	/*
jaroslav@559	2169	* Traditional (without sentinel) insertion sort,
jaroslav@559	2170	* optimized for server VM, is used in case of
jaroslav@559	2171	* the leftmost part.
jaroslav@559	2172	*/
jaroslav@559	2173	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	2174	float ai = a[i + 1];
jaroslav@559	2175	while (ai < a[j]) {
jaroslav@559	2176	a[j + 1] = a[j];
jaroslav@559	2177	if (j-- == left) {
jaroslav@559	2178	break;
jaroslav@559	2179	}
jaroslav@559	2180	}
jaroslav@559	2181	a[j + 1] = ai;
jaroslav@559	2182	}
jaroslav@559	2183	} else {
jaroslav@559	2184	/*
jaroslav@559	2185	* Skip the longest ascending sequence.
jaroslav@559	2186	*/
jaroslav@559	2187	do {
jaroslav@559	2188	if (left >= right) {
jaroslav@559	2189	return;
jaroslav@559	2190	}
jaroslav@559	2191	} while (a[++left] >= a[left - 1]);
jaroslav@559	2192
jaroslav@559	2193	/*
jaroslav@559	2194	* Every element from adjoining part plays the role
jaroslav@559	2195	* of sentinel, therefore this allows us to avoid the
jaroslav@559	2196	* left range check on each iteration. Moreover, we use
jaroslav@559	2197	* the more optimized algorithm, so called pair insertion
jaroslav@559	2198	* sort, which is faster (in the context of Quicksort)
jaroslav@559	2199	* than traditional implementation of insertion sort.
jaroslav@559	2200	*/
jaroslav@559	2201	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	2202	float a1 = a[k], a2 = a[left];
jaroslav@559	2203
jaroslav@559	2204	if (a1 < a2) {
jaroslav@559	2205	a2 = a1; a1 = a[left];
jaroslav@559	2206	}
jaroslav@559	2207	while (a1 < a[--k]) {
jaroslav@559	2208	a[k + 2] = a[k];
jaroslav@559	2209	}
jaroslav@559	2210	a[++k + 1] = a1;
jaroslav@559	2211
jaroslav@559	2212	while (a2 < a[--k]) {
jaroslav@559	2213	a[k + 1] = a[k];
jaroslav@559	2214	}
jaroslav@559	2215	a[k + 1] = a2;
jaroslav@559	2216	}
jaroslav@559	2217	float last = a[right];
jaroslav@559	2218
jaroslav@559	2219	while (last < a[--right]) {
jaroslav@559	2220	a[right + 1] = a[right];
jaroslav@559	2221	}
jaroslav@559	2222	a[right + 1] = last;
jaroslav@559	2223	}
jaroslav@559	2224	return;
jaroslav@559	2225	}
jaroslav@559	2226
jaroslav@559	2227	// Inexpensive approximation of length / 7
jaroslav@559	2228	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	2229
jaroslav@559	2230	/*
jaroslav@559	2231	* Sort five evenly spaced elements around (and including) the
jaroslav@559	2232	* center element in the range. These elements will be used for
jaroslav@559	2233	* pivot selection as described below. The choice for spacing
jaroslav@559	2234	* these elements was empirically determined to work well on
jaroslav@559	2235	* a wide variety of inputs.
jaroslav@559	2236	*/
jaroslav@559	2237	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	2238	int e2 = e3 - seventh;
jaroslav@559	2239	int e1 = e2 - seventh;
jaroslav@559	2240	int e4 = e3 + seventh;
jaroslav@559	2241	int e5 = e4 + seventh;
jaroslav@559	2242
jaroslav@559	2243	// Sort these elements using insertion sort
jaroslav@559	2244	if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2245
jaroslav@559	2246	if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2247	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2248	}
jaroslav@559	2249	if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	2250	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2251	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2252	}
jaroslav@559	2253	}
jaroslav@559	2254	if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	2255	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	2256	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2257	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2258	}
jaroslav@559	2259	}
jaroslav@559	2260	}
jaroslav@559	2261
jaroslav@559	2262	// Pointers
jaroslav@559	2263	int less = left; // The index of the first element of center part
jaroslav@559	2264	int great = right; // The index before the first element of right part
jaroslav@559	2265
jaroslav@559	2266	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	2267	/*
jaroslav@559	2268	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	2269	* These values are inexpensive approximations of the first and
jaroslav@559	2270	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	2271	*/
jaroslav@559	2272	float pivot1 = a[e2];
jaroslav@559	2273	float pivot2 = a[e4];
jaroslav@559	2274
jaroslav@559	2275	/*
jaroslav@559	2276	* The first and the last elements to be sorted are moved to the
jaroslav@559	2277	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	2278	* is complete, the pivots are swapped back into their final
jaroslav@559	2279	* positions, and excluded from subsequent sorting.
jaroslav@559	2280	*/
jaroslav@559	2281	a[e2] = a[left];
jaroslav@559	2282	a[e4] = a[right];
jaroslav@559	2283
jaroslav@559	2284	/*
jaroslav@559	2285	* Skip elements, which are less or greater than pivot values.
jaroslav@559	2286	*/
jaroslav@559	2287	while (a[++less] < pivot1);
jaroslav@559	2288	while (a[--great] > pivot2);
jaroslav@559	2289
jaroslav@559	2290	/*
jaroslav@559	2291	* Partitioning:
jaroslav@559	2292	*
jaroslav@559	2293	* left part center part right part
jaroslav@559	2294	* +--------------------------------------------------------------+
jaroslav@559	2295	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	2296	* +--------------------------------------------------------------+
jaroslav@559	2297	* ^ ^ ^
jaroslav@559	2298	* \| \| \|
jaroslav@559	2299	* less k great
jaroslav@559	2300	*
jaroslav@559	2301	* Invariants:
jaroslav@559	2302	*
jaroslav@559	2303	* all in (left, less) < pivot1
jaroslav@559	2304	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	2305	* all in (great, right) > pivot2
jaroslav@559	2306	*
jaroslav@559	2307	* Pointer k is the first index of ?-part.
jaroslav@559	2308	*/
jaroslav@559	2309	outer:
jaroslav@559	2310	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	2311	float ak = a[k];
jaroslav@559	2312	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	2313	a[k] = a[less];
jaroslav@559	2314	/*
jaroslav@559	2315	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	2316	* of "a[i++] = b;" due to performance issue.
jaroslav@559	2317	*/
jaroslav@559	2318	a[less] = ak;
jaroslav@559	2319	++less;
jaroslav@559	2320	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	2321	while (a[great] > pivot2) {
jaroslav@559	2322	if (great-- == k) {
jaroslav@559	2323	break outer;
jaroslav@559	2324	}
jaroslav@559	2325	}
jaroslav@559	2326	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	2327	a[k] = a[less];
jaroslav@559	2328	a[less] = a[great];
jaroslav@559	2329	++less;
jaroslav@559	2330	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	2331	a[k] = a[great];
jaroslav@559	2332	}
jaroslav@559	2333	/*
jaroslav@559	2334	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	2335	* of "a[i--] = b;" due to performance issue.
jaroslav@559	2336	*/
jaroslav@559	2337	a[great] = ak;
jaroslav@559	2338	--great;
jaroslav@559	2339	}
jaroslav@559	2340	}
jaroslav@559	2341
jaroslav@559	2342	// Swap pivots into their final positions
jaroslav@559	2343	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	2344	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	2345
jaroslav@559	2346	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	2347	sort(a, left, less - 2, leftmost);
jaroslav@559	2348	sort(a, great + 2, right, false);
jaroslav@559	2349
jaroslav@559	2350	/*
jaroslav@559	2351	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	2352	* swap internal pivot values to ends.
jaroslav@559	2353	*/
jaroslav@559	2354	if (less < e1 && e5 < great) {
jaroslav@559	2355	/*
jaroslav@559	2356	* Skip elements, which are equal to pivot values.
jaroslav@559	2357	*/
jaroslav@559	2358	while (a[less] == pivot1) {
jaroslav@559	2359	++less;
jaroslav@559	2360	}
jaroslav@559	2361
jaroslav@559	2362	while (a[great] == pivot2) {
jaroslav@559	2363	--great;
jaroslav@559	2364	}
jaroslav@559	2365
jaroslav@559	2366	/*
jaroslav@559	2367	* Partitioning:
jaroslav@559	2368	*
jaroslav@559	2369	* left part center part right part
jaroslav@559	2370	* +----------------------------------------------------------+
jaroslav@559	2371	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	2372	* +----------------------------------------------------------+
jaroslav@559	2373	* ^ ^ ^
jaroslav@559	2374	* \| \| \|
jaroslav@559	2375	* less k great
jaroslav@559	2376	*
jaroslav@559	2377	* Invariants:
jaroslav@559	2378	*
jaroslav@559	2379	* all in (*, less) == pivot1
jaroslav@559	2380	* pivot1 < all in [less, k) < pivot2
jaroslav@559	2381	* all in (great, *) == pivot2
jaroslav@559	2382	*
jaroslav@559	2383	* Pointer k is the first index of ?-part.
jaroslav@559	2384	*/
jaroslav@559	2385	outer:
jaroslav@559	2386	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	2387	float ak = a[k];
jaroslav@559	2388	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	2389	a[k] = a[less];
jaroslav@559	2390	a[less] = ak;
jaroslav@559	2391	++less;
jaroslav@559	2392	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	2393	while (a[great] == pivot2) {
jaroslav@559	2394	if (great-- == k) {
jaroslav@559	2395	break outer;
jaroslav@559	2396	}
jaroslav@559	2397	}
jaroslav@559	2398	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	2399	a[k] = a[less];
jaroslav@559	2400	/*
jaroslav@559	2401	* Even though a[great] equals to pivot1, the
jaroslav@559	2402	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	2403	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	2404	* of different signs. Therefore in float and
jaroslav@559	2405	* double sorting methods we have to use more
jaroslav@559	2406	* accurate assignment a[less] = a[great].
jaroslav@559	2407	*/
jaroslav@559	2408	a[less] = a[great];
jaroslav@559	2409	++less;
jaroslav@559	2410	} else { // pivot1 < a[great] < pivot2
jaroslav@559	2411	a[k] = a[great];
jaroslav@559	2412	}
jaroslav@559	2413	a[great] = ak;
jaroslav@559	2414	--great;
jaroslav@559	2415	}
jaroslav@559	2416	}
jaroslav@559	2417	}
jaroslav@559	2418
jaroslav@559	2419	// Sort center part recursively
jaroslav@559	2420	sort(a, less, great, false);
jaroslav@559	2421
jaroslav@559	2422	} else { // Partitioning with one pivot
jaroslav@559	2423	/*
jaroslav@559	2424	* Use the third of the five sorted elements as pivot.
jaroslav@559	2425	* This value is inexpensive approximation of the median.
jaroslav@559	2426	*/
jaroslav@559	2427	float pivot = a[e3];
jaroslav@559	2428
jaroslav@559	2429	/*
jaroslav@559	2430	* Partitioning degenerates to the traditional 3-way
jaroslav@559	2431	* (or "Dutch National Flag") schema:
jaroslav@559	2432	*
jaroslav@559	2433	* left part center part right part
jaroslav@559	2434	* +-------------------------------------------------+
jaroslav@559	2435	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	2436	* +-------------------------------------------------+
jaroslav@559	2437	* ^ ^ ^
jaroslav@559	2438	* \| \| \|
jaroslav@559	2439	* less k great
jaroslav@559	2440	*
jaroslav@559	2441	* Invariants:
jaroslav@559	2442	*
jaroslav@559	2443	* all in (left, less) < pivot
jaroslav@559	2444	* all in [less, k) == pivot
jaroslav@559	2445	* all in (great, right) > pivot
jaroslav@559	2446	*
jaroslav@559	2447	* Pointer k is the first index of ?-part.
jaroslav@559	2448	*/
jaroslav@559	2449	for (int k = less; k <= great; ++k) {
jaroslav@559	2450	if (a[k] == pivot) {
jaroslav@559	2451	continue;
jaroslav@559	2452	}
jaroslav@559	2453	float ak = a[k];
jaroslav@559	2454	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	2455	a[k] = a[less];
jaroslav@559	2456	a[less] = ak;
jaroslav@559	2457	++less;
jaroslav@559	2458	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	2459	while (a[great] > pivot) {
jaroslav@559	2460	--great;
jaroslav@559	2461	}
jaroslav@559	2462	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	2463	a[k] = a[less];
jaroslav@559	2464	a[less] = a[great];
jaroslav@559	2465	++less;
jaroslav@559	2466	} else { // a[great] == pivot
jaroslav@559	2467	/*
jaroslav@559	2468	* Even though a[great] equals to pivot, the
jaroslav@559	2469	* assignment a[k] = pivot may be incorrect,
jaroslav@559	2470	* if a[great] and pivot are floating-point
jaroslav@559	2471	* zeros of different signs. Therefore in float
jaroslav@559	2472	* and double sorting methods we have to use
jaroslav@559	2473	* more accurate assignment a[k] = a[great].
jaroslav@559	2474	*/
jaroslav@559	2475	a[k] = a[great];
jaroslav@559	2476	}
jaroslav@559	2477	a[great] = ak;
jaroslav@559	2478	--great;
jaroslav@559	2479	}
jaroslav@559	2480	}
jaroslav@559	2481
jaroslav@559	2482	/*
jaroslav@559	2483	* Sort left and right parts recursively.
jaroslav@559	2484	* All elements from center part are equal
jaroslav@559	2485	* and, therefore, already sorted.
jaroslav@559	2486	*/
jaroslav@559	2487	sort(a, left, less - 1, leftmost);
jaroslav@559	2488	sort(a, great + 1, right, false);
jaroslav@559	2489	}
jaroslav@559	2490	}
jaroslav@559	2491
jaroslav@559	2492	/**
jaroslav@559	2493	* Sorts the specified array.
jaroslav@559	2494	*
jaroslav@559	2495	* @param a the array to be sorted
jaroslav@559	2496	*/
jaroslav@559	2497	public static void sort(double[] a) {
jaroslav@559	2498	sort(a, 0, a.length - 1);
jaroslav@559	2499	}
jaroslav@559	2500
jaroslav@559	2501	/**
jaroslav@559	2502	* Sorts the specified range of the array.
jaroslav@559	2503	*
jaroslav@559	2504	* @param a the array to be sorted
jaroslav@559	2505	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	2506	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	2507	*/
jaroslav@559	2508	public static void sort(double[] a, int left, int right) {
jaroslav@559	2509	/*
jaroslav@559	2510	* Phase 1: Move NaNs to the end of the array.
jaroslav@559	2511	*/
jaroslav@559	2512	while (left <= right && Double.isNaN(a[right])) {
jaroslav@559	2513	--right;
jaroslav@559	2514	}
jaroslav@559	2515	for (int k = right; --k >= left; ) {
jaroslav@559	2516	double ak = a[k];
jaroslav@559	2517	if (ak != ak) { // a[k] is NaN
jaroslav@559	2518	a[k] = a[right];
jaroslav@559	2519	a[right] = ak;
jaroslav@559	2520	--right;
jaroslav@559	2521	}
jaroslav@559	2522	}
jaroslav@559	2523
jaroslav@559	2524	/*
jaroslav@559	2525	* Phase 2: Sort everything except NaNs (which are already in place).
jaroslav@559	2526	*/
jaroslav@559	2527	doSort(a, left, right);
jaroslav@559	2528
jaroslav@559	2529	/*
jaroslav@559	2530	* Phase 3: Place negative zeros before positive zeros.
jaroslav@559	2531	*/
jaroslav@559	2532	int hi = right;
jaroslav@559	2533
jaroslav@559	2534	/*
jaroslav@559	2535	* Find the first zero, or first positive, or last negative element.
jaroslav@559	2536	*/
jaroslav@559	2537	while (left < hi) {
jaroslav@559	2538	int middle = (left + hi) >>> 1;
jaroslav@559	2539	double middleValue = a[middle];
jaroslav@559	2540
jaroslav@559	2541	if (middleValue < 0.0d) {
jaroslav@559	2542	left = middle + 1;
jaroslav@559	2543	} else {
jaroslav@559	2544	hi = middle;
jaroslav@559	2545	}
jaroslav@559	2546	}
jaroslav@559	2547
jaroslav@559	2548	/*
jaroslav@559	2549	* Skip the last negative value (if any) or all leading negative zeros.
jaroslav@559	2550	*/
jaroslav@559	2551	while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
jaroslav@559	2552	++left;
jaroslav@559	2553	}
jaroslav@559	2554
jaroslav@559	2555	/*
jaroslav@559	2556	* Move negative zeros to the beginning of the sub-range.
jaroslav@559	2557	*
jaroslav@559	2558	* Partitioning:
jaroslav@559	2559	*
jaroslav@559	2560	* +----------------------------------------------------+
jaroslav@559	2561	* \| < 0.0 \| -0.0 \| 0.0 \| ? ( >= 0.0 ) \|
jaroslav@559	2562	* +----------------------------------------------------+
jaroslav@559	2563	* ^ ^ ^
jaroslav@559	2564	* \| \| \|
jaroslav@559	2565	* left p k
jaroslav@559	2566	*
jaroslav@559	2567	* Invariants:
jaroslav@559	2568	*
jaroslav@559	2569	* all in (*, left) < 0.0
jaroslav@559	2570	* all in [left, p) == -0.0
jaroslav@559	2571	* all in [p, k) == 0.0
jaroslav@559	2572	* all in [k, right] >= 0.0
jaroslav@559	2573	*
jaroslav@559	2574	* Pointer k is the first index of ?-part.
jaroslav@559	2575	*/
jaroslav@559	2576	for (int k = left, p = left - 1; ++k <= right; ) {
jaroslav@559	2577	double ak = a[k];
jaroslav@559	2578	if (ak != 0.0d) {
jaroslav@559	2579	break;
jaroslav@559	2580	}
jaroslav@559	2581	if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
jaroslav@559	2582	a[k] = 0.0d;
jaroslav@559	2583	a[++p] = -0.0d;
jaroslav@559	2584	}
jaroslav@559	2585	}
jaroslav@559	2586	}
jaroslav@559	2587
jaroslav@559	2588	/**
jaroslav@559	2589	* Sorts the specified range of the array.
jaroslav@559	2590	*
jaroslav@559	2591	* @param a the array to be sorted
jaroslav@559	2592	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	2593	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	2594	*/
jaroslav@559	2595	private static void doSort(double[] a, int left, int right) {
jaroslav@559	2596	// Use Quicksort on small arrays
jaroslav@559	2597	if (right - left < QUICKSORT_THRESHOLD) {
jaroslav@559	2598	sort(a, left, right, true);
jaroslav@559	2599	return;
jaroslav@559	2600	}
jaroslav@559	2601
jaroslav@559	2602	/*
jaroslav@559	2603	* Index run[i] is the start of i-th run
jaroslav@559	2604	* (ascending or descending sequence).
jaroslav@559	2605	*/
jaroslav@559	2606	int[] run = new int[MAX_RUN_COUNT + 1];
jaroslav@559	2607	int count = 0; run[0] = left;
jaroslav@559	2608
jaroslav@559	2609	// Check if the array is nearly sorted
jaroslav@559	2610	for (int k = left; k < right; run[count] = k) {
jaroslav@559	2611	if (a[k] < a[k + 1]) { // ascending
jaroslav@559	2612	while (++k <= right && a[k - 1] <= a[k]);
jaroslav@559	2613	} else if (a[k] > a[k + 1]) { // descending
jaroslav@559	2614	while (++k <= right && a[k - 1] >= a[k]);
jaroslav@559	2615	for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
jaroslav@559	2616	double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
jaroslav@559	2617	}
jaroslav@559	2618	} else { // equal
jaroslav@559	2619	for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
jaroslav@559	2620	if (--m == 0) {
jaroslav@559	2621	sort(a, left, right, true);
jaroslav@559	2622	return;
jaroslav@559	2623	}
jaroslav@559	2624	}
jaroslav@559	2625	}
jaroslav@559	2626
jaroslav@559	2627	/*
jaroslav@559	2628	* The array is not highly structured,
jaroslav@559	2629	* use Quicksort instead of merge sort.
jaroslav@559	2630	*/
jaroslav@559	2631	if (++count == MAX_RUN_COUNT) {
jaroslav@559	2632	sort(a, left, right, true);
jaroslav@559	2633	return;
jaroslav@559	2634	}
jaroslav@559	2635	}
jaroslav@559	2636
jaroslav@559	2637	// Check special cases
jaroslav@559	2638	if (run[count] == right++) { // The last run contains one element
jaroslav@559	2639	run[++count] = right;
jaroslav@559	2640	} else if (count == 1) { // The array is already sorted
jaroslav@559	2641	return;
jaroslav@559	2642	}
jaroslav@559	2643
jaroslav@559	2644	/*
jaroslav@559	2645	* Create temporary array, which is used for merging.
jaroslav@559	2646	* Implementation note: variable "right" is increased by 1.
jaroslav@559	2647	*/
jaroslav@559	2648	double[] b; byte odd = 0;
jaroslav@559	2649	for (int n = 1; (n <<= 1) < count; odd ^= 1);
jaroslav@559	2650
jaroslav@559	2651	if (odd == 0) {
jaroslav@559	2652	b = a; a = new double[b.length];
jaroslav@559	2653	for (int i = left - 1; ++i < right; a[i] = b[i]);
jaroslav@559	2654	} else {
jaroslav@559	2655	b = new double[a.length];
jaroslav@559	2656	}
jaroslav@559	2657
jaroslav@559	2658	// Merging
jaroslav@559	2659	for (int last; count > 1; count = last) {
jaroslav@559	2660	for (int k = (last = 0) + 2; k <= count; k += 2) {
jaroslav@559	2661	int hi = run[k], mi = run[k - 1];
jaroslav@559	2662	for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
jaroslav@559	2663	if (q >= hi \|\| p < mi && a[p] <= a[q]) {
jaroslav@559	2664	b[i] = a[p++];
jaroslav@559	2665	} else {
jaroslav@559	2666	b[i] = a[q++];
jaroslav@559	2667	}
jaroslav@559	2668	}
jaroslav@559	2669	run[++last] = hi;
jaroslav@559	2670	}
jaroslav@559	2671	if ((count & 1) != 0) {
jaroslav@559	2672	for (int i = right, lo = run[count - 1]; --i >= lo;
jaroslav@559	2673	b[i] = a[i]
jaroslav@559	2674	);
jaroslav@559	2675	run[++last] = right;
jaroslav@559	2676	}
jaroslav@559	2677	double[] t = a; a = b; b = t;
jaroslav@559	2678	}
jaroslav@559	2679	}
jaroslav@559	2680
jaroslav@559	2681	/**
jaroslav@559	2682	* Sorts the specified range of the array by Dual-Pivot Quicksort.
jaroslav@559	2683	*
jaroslav@559	2684	* @param a the array to be sorted
jaroslav@559	2685	* @param left the index of the first element, inclusive, to be sorted
jaroslav@559	2686	* @param right the index of the last element, inclusive, to be sorted
jaroslav@559	2687	* @param leftmost indicates if this part is the leftmost in the range
jaroslav@559	2688	*/
jaroslav@559	2689	private static void sort(double[] a, int left, int right, boolean leftmost) {
jaroslav@559	2690	int length = right - left + 1;
jaroslav@559	2691
jaroslav@559	2692	// Use insertion sort on tiny arrays
jaroslav@559	2693	if (length < INSERTION_SORT_THRESHOLD) {
jaroslav@559	2694	if (leftmost) {
jaroslav@559	2695	/*
jaroslav@559	2696	* Traditional (without sentinel) insertion sort,
jaroslav@559	2697	* optimized for server VM, is used in case of
jaroslav@559	2698	* the leftmost part.
jaroslav@559	2699	*/
jaroslav@559	2700	for (int i = left, j = i; i < right; j = ++i) {
jaroslav@559	2701	double ai = a[i + 1];
jaroslav@559	2702	while (ai < a[j]) {
jaroslav@559	2703	a[j + 1] = a[j];
jaroslav@559	2704	if (j-- == left) {
jaroslav@559	2705	break;
jaroslav@559	2706	}
jaroslav@559	2707	}
jaroslav@559	2708	a[j + 1] = ai;
jaroslav@559	2709	}
jaroslav@559	2710	} else {
jaroslav@559	2711	/*
jaroslav@559	2712	* Skip the longest ascending sequence.
jaroslav@559	2713	*/
jaroslav@559	2714	do {
jaroslav@559	2715	if (left >= right) {
jaroslav@559	2716	return;
jaroslav@559	2717	}
jaroslav@559	2718	} while (a[++left] >= a[left - 1]);
jaroslav@559	2719
jaroslav@559	2720	/*
jaroslav@559	2721	* Every element from adjoining part plays the role
jaroslav@559	2722	* of sentinel, therefore this allows us to avoid the
jaroslav@559	2723	* left range check on each iteration. Moreover, we use
jaroslav@559	2724	* the more optimized algorithm, so called pair insertion
jaroslav@559	2725	* sort, which is faster (in the context of Quicksort)
jaroslav@559	2726	* than traditional implementation of insertion sort.
jaroslav@559	2727	*/
jaroslav@559	2728	for (int k = left; ++left <= right; k = ++left) {
jaroslav@559	2729	double a1 = a[k], a2 = a[left];
jaroslav@559	2730
jaroslav@559	2731	if (a1 < a2) {
jaroslav@559	2732	a2 = a1; a1 = a[left];
jaroslav@559	2733	}
jaroslav@559	2734	while (a1 < a[--k]) {
jaroslav@559	2735	a[k + 2] = a[k];
jaroslav@559	2736	}
jaroslav@559	2737	a[++k + 1] = a1;
jaroslav@559	2738
jaroslav@559	2739	while (a2 < a[--k]) {
jaroslav@559	2740	a[k + 1] = a[k];
jaroslav@559	2741	}
jaroslav@559	2742	a[k + 1] = a2;
jaroslav@559	2743	}
jaroslav@559	2744	double last = a[right];
jaroslav@559	2745
jaroslav@559	2746	while (last < a[--right]) {
jaroslav@559	2747	a[right + 1] = a[right];
jaroslav@559	2748	}
jaroslav@559	2749	a[right + 1] = last;
jaroslav@559	2750	}
jaroslav@559	2751	return;
jaroslav@559	2752	}
jaroslav@559	2753
jaroslav@559	2754	// Inexpensive approximation of length / 7
jaroslav@559	2755	int seventh = (length >> 3) + (length >> 6) + 1;
jaroslav@559	2756
jaroslav@559	2757	/*
jaroslav@559	2758	* Sort five evenly spaced elements around (and including) the
jaroslav@559	2759	* center element in the range. These elements will be used for
jaroslav@559	2760	* pivot selection as described below. The choice for spacing
jaroslav@559	2761	* these elements was empirically determined to work well on
jaroslav@559	2762	* a wide variety of inputs.
jaroslav@559	2763	*/
jaroslav@559	2764	int e3 = (left + right) >>> 1; // The midpoint
jaroslav@559	2765	int e2 = e3 - seventh;
jaroslav@559	2766	int e1 = e2 - seventh;
jaroslav@559	2767	int e4 = e3 + seventh;
jaroslav@559	2768	int e5 = e4 + seventh;
jaroslav@559	2769
jaroslav@559	2770	// Sort these elements using insertion sort
jaroslav@559	2771	if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2772
jaroslav@559	2773	if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2774	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2775	}
jaroslav@559	2776	if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
jaroslav@559	2777	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2778	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2779	}
jaroslav@559	2780	}
jaroslav@559	2781	if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
jaroslav@559	2782	if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
jaroslav@559	2783	if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
jaroslav@559	2784	if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
jaroslav@559	2785	}
jaroslav@559	2786	}
jaroslav@559	2787	}
jaroslav@559	2788
jaroslav@559	2789	// Pointers
jaroslav@559	2790	int less = left; // The index of the first element of center part
jaroslav@559	2791	int great = right; // The index before the first element of right part
jaroslav@559	2792
jaroslav@559	2793	if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
jaroslav@559	2794	/*
jaroslav@559	2795	* Use the second and fourth of the five sorted elements as pivots.
jaroslav@559	2796	* These values are inexpensive approximations of the first and
jaroslav@559	2797	* second terciles of the array. Note that pivot1 <= pivot2.
jaroslav@559	2798	*/
jaroslav@559	2799	double pivot1 = a[e2];
jaroslav@559	2800	double pivot2 = a[e4];
jaroslav@559	2801
jaroslav@559	2802	/*
jaroslav@559	2803	* The first and the last elements to be sorted are moved to the
jaroslav@559	2804	* locations formerly occupied by the pivots. When partitioning
jaroslav@559	2805	* is complete, the pivots are swapped back into their final
jaroslav@559	2806	* positions, and excluded from subsequent sorting.
jaroslav@559	2807	*/
jaroslav@559	2808	a[e2] = a[left];
jaroslav@559	2809	a[e4] = a[right];
jaroslav@559	2810
jaroslav@559	2811	/*
jaroslav@559	2812	* Skip elements, which are less or greater than pivot values.
jaroslav@559	2813	*/
jaroslav@559	2814	while (a[++less] < pivot1);
jaroslav@559	2815	while (a[--great] > pivot2);
jaroslav@559	2816
jaroslav@559	2817	/*
jaroslav@559	2818	* Partitioning:
jaroslav@559	2819	*
jaroslav@559	2820	* left part center part right part
jaroslav@559	2821	* +--------------------------------------------------------------+
jaroslav@559	2822	* \| < pivot1 \| pivot1 <= && <= pivot2 \| ? \| > pivot2 \|
jaroslav@559	2823	* +--------------------------------------------------------------+
jaroslav@559	2824	* ^ ^ ^
jaroslav@559	2825	* \| \| \|
jaroslav@559	2826	* less k great
jaroslav@559	2827	*
jaroslav@559	2828	* Invariants:
jaroslav@559	2829	*
jaroslav@559	2830	* all in (left, less) < pivot1
jaroslav@559	2831	* pivot1 <= all in [less, k) <= pivot2
jaroslav@559	2832	* all in (great, right) > pivot2
jaroslav@559	2833	*
jaroslav@559	2834	* Pointer k is the first index of ?-part.
jaroslav@559	2835	*/
jaroslav@559	2836	outer:
jaroslav@559	2837	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	2838	double ak = a[k];
jaroslav@559	2839	if (ak < pivot1) { // Move a[k] to left part
jaroslav@559	2840	a[k] = a[less];
jaroslav@559	2841	/*
jaroslav@559	2842	* Here and below we use "a[i] = b; i++;" instead
jaroslav@559	2843	* of "a[i++] = b;" due to performance issue.
jaroslav@559	2844	*/
jaroslav@559	2845	a[less] = ak;
jaroslav@559	2846	++less;
jaroslav@559	2847	} else if (ak > pivot2) { // Move a[k] to right part
jaroslav@559	2848	while (a[great] > pivot2) {
jaroslav@559	2849	if (great-- == k) {
jaroslav@559	2850	break outer;
jaroslav@559	2851	}
jaroslav@559	2852	}
jaroslav@559	2853	if (a[great] < pivot1) { // a[great] <= pivot2
jaroslav@559	2854	a[k] = a[less];
jaroslav@559	2855	a[less] = a[great];
jaroslav@559	2856	++less;
jaroslav@559	2857	} else { // pivot1 <= a[great] <= pivot2
jaroslav@559	2858	a[k] = a[great];
jaroslav@559	2859	}
jaroslav@559	2860	/*
jaroslav@559	2861	* Here and below we use "a[i] = b; i--;" instead
jaroslav@559	2862	* of "a[i--] = b;" due to performance issue.
jaroslav@559	2863	*/
jaroslav@559	2864	a[great] = ak;
jaroslav@559	2865	--great;
jaroslav@559	2866	}
jaroslav@559	2867	}
jaroslav@559	2868
jaroslav@559	2869	// Swap pivots into their final positions
jaroslav@559	2870	a[left] = a[less - 1]; a[less - 1] = pivot1;
jaroslav@559	2871	a[right] = a[great + 1]; a[great + 1] = pivot2;
jaroslav@559	2872
jaroslav@559	2873	// Sort left and right parts recursively, excluding known pivots
jaroslav@559	2874	sort(a, left, less - 2, leftmost);
jaroslav@559	2875	sort(a, great + 2, right, false);
jaroslav@559	2876
jaroslav@559	2877	/*
jaroslav@559	2878	* If center part is too large (comprises > 4/7 of the array),
jaroslav@559	2879	* swap internal pivot values to ends.
jaroslav@559	2880	*/
jaroslav@559	2881	if (less < e1 && e5 < great) {
jaroslav@559	2882	/*
jaroslav@559	2883	* Skip elements, which are equal to pivot values.
jaroslav@559	2884	*/
jaroslav@559	2885	while (a[less] == pivot1) {
jaroslav@559	2886	++less;
jaroslav@559	2887	}
jaroslav@559	2888
jaroslav@559	2889	while (a[great] == pivot2) {
jaroslav@559	2890	--great;
jaroslav@559	2891	}
jaroslav@559	2892
jaroslav@559	2893	/*
jaroslav@559	2894	* Partitioning:
jaroslav@559	2895	*
jaroslav@559	2896	* left part center part right part
jaroslav@559	2897	* +----------------------------------------------------------+
jaroslav@559	2898	* \| == pivot1 \| pivot1 < && < pivot2 \| ? \| == pivot2 \|
jaroslav@559	2899	* +----------------------------------------------------------+
jaroslav@559	2900	* ^ ^ ^
jaroslav@559	2901	* \| \| \|
jaroslav@559	2902	* less k great
jaroslav@559	2903	*
jaroslav@559	2904	* Invariants:
jaroslav@559	2905	*
jaroslav@559	2906	* all in (*, less) == pivot1
jaroslav@559	2907	* pivot1 < all in [less, k) < pivot2
jaroslav@559	2908	* all in (great, *) == pivot2
jaroslav@559	2909	*
jaroslav@559	2910	* Pointer k is the first index of ?-part.
jaroslav@559	2911	*/
jaroslav@559	2912	outer:
jaroslav@559	2913	for (int k = less - 1; ++k <= great; ) {
jaroslav@559	2914	double ak = a[k];
jaroslav@559	2915	if (ak == pivot1) { // Move a[k] to left part
jaroslav@559	2916	a[k] = a[less];
jaroslav@559	2917	a[less] = ak;
jaroslav@559	2918	++less;
jaroslav@559	2919	} else if (ak == pivot2) { // Move a[k] to right part
jaroslav@559	2920	while (a[great] == pivot2) {
jaroslav@559	2921	if (great-- == k) {
jaroslav@559	2922	break outer;
jaroslav@559	2923	}
jaroslav@559	2924	}
jaroslav@559	2925	if (a[great] == pivot1) { // a[great] < pivot2
jaroslav@559	2926	a[k] = a[less];
jaroslav@559	2927	/*
jaroslav@559	2928	* Even though a[great] equals to pivot1, the
jaroslav@559	2929	* assignment a[less] = pivot1 may be incorrect,
jaroslav@559	2930	* if a[great] and pivot1 are floating-point zeros
jaroslav@559	2931	* of different signs. Therefore in float and
jaroslav@559	2932	* double sorting methods we have to use more
jaroslav@559	2933	* accurate assignment a[less] = a[great].
jaroslav@559	2934	*/
jaroslav@559	2935	a[less] = a[great];
jaroslav@559	2936	++less;
jaroslav@559	2937	} else { // pivot1 < a[great] < pivot2
jaroslav@559	2938	a[k] = a[great];
jaroslav@559	2939	}
jaroslav@559	2940	a[great] = ak;
jaroslav@559	2941	--great;
jaroslav@559	2942	}
jaroslav@559	2943	}
jaroslav@559	2944	}
jaroslav@559	2945
jaroslav@559	2946	// Sort center part recursively
jaroslav@559	2947	sort(a, less, great, false);
jaroslav@559	2948
jaroslav@559	2949	} else { // Partitioning with one pivot
jaroslav@559	2950	/*
jaroslav@559	2951	* Use the third of the five sorted elements as pivot.
jaroslav@559	2952	* This value is inexpensive approximation of the median.
jaroslav@559	2953	*/
jaroslav@559	2954	double pivot = a[e3];
jaroslav@559	2955
jaroslav@559	2956	/*
jaroslav@559	2957	* Partitioning degenerates to the traditional 3-way
jaroslav@559	2958	* (or "Dutch National Flag") schema:
jaroslav@559	2959	*
jaroslav@559	2960	* left part center part right part
jaroslav@559	2961	* +-------------------------------------------------+
jaroslav@559	2962	* \| < pivot \| == pivot \| ? \| > pivot \|
jaroslav@559	2963	* +-------------------------------------------------+
jaroslav@559	2964	* ^ ^ ^
jaroslav@559	2965	* \| \| \|
jaroslav@559	2966	* less k great
jaroslav@559	2967	*
jaroslav@559	2968	* Invariants:
jaroslav@559	2969	*
jaroslav@559	2970	* all in (left, less) < pivot
jaroslav@559	2971	* all in [less, k) == pivot
jaroslav@559	2972	* all in (great, right) > pivot
jaroslav@559	2973	*
jaroslav@559	2974	* Pointer k is the first index of ?-part.
jaroslav@559	2975	*/
jaroslav@559	2976	for (int k = less; k <= great; ++k) {
jaroslav@559	2977	if (a[k] == pivot) {
jaroslav@559	2978	continue;
jaroslav@559	2979	}
jaroslav@559	2980	double ak = a[k];
jaroslav@559	2981	if (ak < pivot) { // Move a[k] to left part
jaroslav@559	2982	a[k] = a[less];
jaroslav@559	2983	a[less] = ak;
jaroslav@559	2984	++less;
jaroslav@559	2985	} else { // a[k] > pivot - Move a[k] to right part
jaroslav@559	2986	while (a[great] > pivot) {
jaroslav@559	2987	--great;
jaroslav@559	2988	}
jaroslav@559	2989	if (a[great] < pivot) { // a[great] <= pivot
jaroslav@559	2990	a[k] = a[less];
jaroslav@559	2991	a[less] = a[great];
jaroslav@559	2992	++less;
jaroslav@559	2993	} else { // a[great] == pivot
jaroslav@559	2994	/*
jaroslav@559	2995	* Even though a[great] equals to pivot, the
jaroslav@559	2996	* assignment a[k] = pivot may be incorrect,
jaroslav@559	2997	* if a[great] and pivot are floating-point
jaroslav@559	2998	* zeros of different signs. Therefore in float
jaroslav@559	2999	* and double sorting methods we have to use
jaroslav@559	3000	* more accurate assignment a[k] = a[great].
jaroslav@559	3001	*/
jaroslav@559	3002	a[k] = a[great];
jaroslav@559	3003	}
jaroslav@559	3004	a[great] = ak;
jaroslav@559	3005	--great;
jaroslav@559	3006	}
jaroslav@559	3007	}
jaroslav@559	3008
jaroslav@559	3009	/*
jaroslav@559	3010	* Sort left and right parts recursively.
jaroslav@559	3011	* All elements from center part are equal
jaroslav@559	3012	* and, therefore, already sorted.
jaroslav@559	3013	*/
jaroslav@559	3014	sort(a, left, less - 1, leftmost);
jaroslav@559	3015	sort(a, great + 1, right, false);
jaroslav@559	3016	}
jaroslav@559	3017	}
jaroslav@559	3018	}

author	Jaroslav Tulach <jaroslav.tulach@apidesign.org>
	Tue, 26 Feb 2013 16:54:16 +0100
changeset 772	d382dacfd73f
parent 559	emul/compact/src/main/java/java/util/DualPivotQuicksort.java@9ec5ddf175b5
permissions	-rw-r--r--