jaroslav@559: /* jaroslav@559: * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. jaroslav@559: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@559: * jaroslav@559: * This code is free software; you can redistribute it and/or modify it jaroslav@559: * under the terms of the GNU General Public License version 2 only, as jaroslav@559: * published by the Free Software Foundation. Oracle designates this jaroslav@559: * particular file as subject to the "Classpath" exception as provided jaroslav@559: * by Oracle in the LICENSE file that accompanied this code. jaroslav@559: * jaroslav@559: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@559: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@559: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@559: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@559: * accompanied this code). jaroslav@559: * jaroslav@559: * You should have received a copy of the GNU General Public License version jaroslav@559: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@559: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@559: * jaroslav@559: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@559: * or visit www.oracle.com if you need additional information or have any jaroslav@559: * questions. jaroslav@559: */ jaroslav@559: jaroslav@559: package java.util; jaroslav@559: jaroslav@559: /** jaroslav@559: * This class implements the Dual-Pivot Quicksort algorithm by jaroslav@559: * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm jaroslav@559: * offers O(n log(n)) performance on many data sets that cause other jaroslav@559: * quicksorts to degrade to quadratic performance, and is typically jaroslav@559: * faster than traditional (one-pivot) Quicksort implementations. jaroslav@559: * jaroslav@559: * @author Vladimir Yaroslavskiy jaroslav@559: * @author Jon Bentley jaroslav@559: * @author Josh Bloch jaroslav@559: * jaroslav@559: * @version 2011.02.11 m765.827.12i:5\7pm jaroslav@559: * @since 1.7 jaroslav@559: */ jaroslav@559: final class DualPivotQuicksort { jaroslav@559: jaroslav@559: /** jaroslav@559: * Prevents instantiation. jaroslav@559: */ jaroslav@559: private DualPivotQuicksort() {} jaroslav@559: jaroslav@559: /* jaroslav@559: * Tuning parameters. jaroslav@559: */ jaroslav@559: jaroslav@559: /** jaroslav@559: * The maximum number of runs in merge sort. jaroslav@559: */ jaroslav@559: private static final int MAX_RUN_COUNT = 67; jaroslav@559: jaroslav@559: /** jaroslav@559: * The maximum length of run in merge sort. jaroslav@559: */ jaroslav@559: private static final int MAX_RUN_LENGTH = 33; jaroslav@559: jaroslav@559: /** jaroslav@559: * If the length of an array to be sorted is less than this jaroslav@559: * constant, Quicksort is used in preference to merge sort. jaroslav@559: */ jaroslav@559: private static final int QUICKSORT_THRESHOLD = 286; jaroslav@559: jaroslav@559: /** jaroslav@559: * If the length of an array to be sorted is less than this jaroslav@559: * constant, insertion sort is used in preference to Quicksort. jaroslav@559: */ jaroslav@559: private static final int INSERTION_SORT_THRESHOLD = 47; jaroslav@559: jaroslav@559: /** jaroslav@559: * If the length of a byte array to be sorted is greater than this jaroslav@559: * constant, counting sort is used in preference to insertion sort. jaroslav@559: */ jaroslav@559: private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29; jaroslav@559: jaroslav@559: /** jaroslav@559: * If the length of a short or char array to be sorted is greater jaroslav@559: * than this constant, counting sort is used in preference to Quicksort. jaroslav@559: */ jaroslav@559: private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sorting methods for seven primitive types. jaroslav@559: */ jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(int[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(int[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: int t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: int[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new int[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new int[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: int[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(int[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: int ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: int a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: int last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: int pivot1 = a[e2]; jaroslav@559: int pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: int ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: int ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = pivot1; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: int pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: int ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = pivot; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(long[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(long[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: long t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: long[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new long[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new long[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: long[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(long[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: long ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: long a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: long last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: long pivot1 = a[e2]; jaroslav@559: long pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: long ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: long ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = pivot1; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: long pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: long ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = pivot; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(short[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(short[] a, int left, int right) { jaroslav@559: // Use counting sort on large arrays jaroslav@559: if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { jaroslav@559: int[] count = new int[NUM_SHORT_VALUES]; jaroslav@559: jaroslav@559: for (int i = left - 1; ++i <= right; jaroslav@559: count[a[i] - Short.MIN_VALUE]++ jaroslav@559: ); jaroslav@559: for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) { jaroslav@559: while (count[--i] == 0); jaroslav@559: short value = (short) (i + Short.MIN_VALUE); jaroslav@559: int s = count[i]; jaroslav@559: jaroslav@559: do { jaroslav@559: a[--k] = value; jaroslav@559: } while (--s > 0); jaroslav@559: } jaroslav@559: } else { // Use Dual-Pivot Quicksort on small arrays jaroslav@559: doSort(a, left, right); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** The number of distinct short values. */ jaroslav@559: private static final int NUM_SHORT_VALUES = 1 << 16; jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: private static void doSort(short[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: short t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: short[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new short[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new short[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: short[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(short[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: short ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: short a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: short last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: short pivot1 = a[e2]; jaroslav@559: short pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: short ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: short ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = pivot1; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: short pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: short ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = pivot; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(char[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(char[] a, int left, int right) { jaroslav@559: // Use counting sort on large arrays jaroslav@559: if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { jaroslav@559: int[] count = new int[NUM_CHAR_VALUES]; jaroslav@559: jaroslav@559: for (int i = left - 1; ++i <= right; jaroslav@559: count[a[i]]++ jaroslav@559: ); jaroslav@559: for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) { jaroslav@559: while (count[--i] == 0); jaroslav@559: char value = (char) i; jaroslav@559: int s = count[i]; jaroslav@559: jaroslav@559: do { jaroslav@559: a[--k] = value; jaroslav@559: } while (--s > 0); jaroslav@559: } jaroslav@559: } else { // Use Dual-Pivot Quicksort on small arrays jaroslav@559: doSort(a, left, right); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** The number of distinct char values. */ jaroslav@559: private static final int NUM_CHAR_VALUES = 1 << 16; jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: private static void doSort(char[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: char t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: char[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new char[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new char[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: char[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(char[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: char ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: char a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: char last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: char pivot1 = a[e2]; jaroslav@559: char pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: char ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: char ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = pivot1; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: char pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: char ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = pivot; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** The number of distinct byte values. */ jaroslav@559: private static final int NUM_BYTE_VALUES = 1 << 8; jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(byte[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(byte[] a, int left, int right) { jaroslav@559: // Use counting sort on large arrays jaroslav@559: if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) { jaroslav@559: int[] count = new int[NUM_BYTE_VALUES]; jaroslav@559: jaroslav@559: for (int i = left - 1; ++i <= right; jaroslav@559: count[a[i] - Byte.MIN_VALUE]++ jaroslav@559: ); jaroslav@559: for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) { jaroslav@559: while (count[--i] == 0); jaroslav@559: byte value = (byte) (i + Byte.MIN_VALUE); jaroslav@559: int s = count[i]; jaroslav@559: jaroslav@559: do { jaroslav@559: a[--k] = value; jaroslav@559: } while (--s > 0); jaroslav@559: } jaroslav@559: } else { // Use insertion sort on small arrays jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: byte ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(float[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(float[] a, int left, int right) { jaroslav@559: /* jaroslav@559: * Phase 1: Move NaNs to the end of the array. jaroslav@559: */ jaroslav@559: while (left <= right && Float.isNaN(a[right])) { jaroslav@559: --right; jaroslav@559: } jaroslav@559: for (int k = right; --k >= left; ) { jaroslav@559: float ak = a[k]; jaroslav@559: if (ak != ak) { // a[k] is NaN jaroslav@559: a[k] = a[right]; jaroslav@559: a[right] = ak; jaroslav@559: --right; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Phase 2: Sort everything except NaNs (which are already in place). jaroslav@559: */ jaroslav@559: doSort(a, left, right); jaroslav@559: jaroslav@559: /* jaroslav@559: * Phase 3: Place negative zeros before positive zeros. jaroslav@559: */ jaroslav@559: int hi = right; jaroslav@559: jaroslav@559: /* jaroslav@559: * Find the first zero, or first positive, or last negative element. jaroslav@559: */ jaroslav@559: while (left < hi) { jaroslav@559: int middle = (left + hi) >>> 1; jaroslav@559: float middleValue = a[middle]; jaroslav@559: jaroslav@559: if (middleValue < 0.0f) { jaroslav@559: left = middle + 1; jaroslav@559: } else { jaroslav@559: hi = middle; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip the last negative value (if any) or all leading negative zeros. jaroslav@559: */ jaroslav@559: while (left <= right && Float.floatToRawIntBits(a[left]) < 0) { jaroslav@559: ++left; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Move negative zeros to the beginning of the sub-range. jaroslav@559: * jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * +----------------------------------------------------+ jaroslav@559: * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | jaroslav@559: * +----------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * left p k jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, left) < 0.0 jaroslav@559: * all in [left, p) == -0.0 jaroslav@559: * all in [p, k) == 0.0 jaroslav@559: * all in [k, right] >= 0.0 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = left, p = left - 1; ++k <= right; ) { jaroslav@559: float ak = a[k]; jaroslav@559: if (ak != 0.0f) { jaroslav@559: break; jaroslav@559: } jaroslav@559: if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f jaroslav@559: a[k] = 0.0f; jaroslav@559: a[++p] = -0.0f; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: private static void doSort(float[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: float t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: float[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new float[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new float[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: float[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(float[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: float ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: float a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: float last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: float pivot1 = a[e2]; jaroslav@559: float pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: float ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: float ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: float pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: float ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: */ jaroslav@559: public static void sort(double[] a) { jaroslav@559: sort(a, 0, a.length - 1); jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: public static void sort(double[] a, int left, int right) { jaroslav@559: /* jaroslav@559: * Phase 1: Move NaNs to the end of the array. jaroslav@559: */ jaroslav@559: while (left <= right && Double.isNaN(a[right])) { jaroslav@559: --right; jaroslav@559: } jaroslav@559: for (int k = right; --k >= left; ) { jaroslav@559: double ak = a[k]; jaroslav@559: if (ak != ak) { // a[k] is NaN jaroslav@559: a[k] = a[right]; jaroslav@559: a[right] = ak; jaroslav@559: --right; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Phase 2: Sort everything except NaNs (which are already in place). jaroslav@559: */ jaroslav@559: doSort(a, left, right); jaroslav@559: jaroslav@559: /* jaroslav@559: * Phase 3: Place negative zeros before positive zeros. jaroslav@559: */ jaroslav@559: int hi = right; jaroslav@559: jaroslav@559: /* jaroslav@559: * Find the first zero, or first positive, or last negative element. jaroslav@559: */ jaroslav@559: while (left < hi) { jaroslav@559: int middle = (left + hi) >>> 1; jaroslav@559: double middleValue = a[middle]; jaroslav@559: jaroslav@559: if (middleValue < 0.0d) { jaroslav@559: left = middle + 1; jaroslav@559: } else { jaroslav@559: hi = middle; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip the last negative value (if any) or all leading negative zeros. jaroslav@559: */ jaroslav@559: while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) { jaroslav@559: ++left; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Move negative zeros to the beginning of the sub-range. jaroslav@559: * jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * +----------------------------------------------------+ jaroslav@559: * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | jaroslav@559: * +----------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * left p k jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, left) < 0.0 jaroslav@559: * all in [left, p) == -0.0 jaroslav@559: * all in [p, k) == 0.0 jaroslav@559: * all in [k, right] >= 0.0 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = left, p = left - 1; ++k <= right; ) { jaroslav@559: double ak = a[k]; jaroslav@559: if (ak != 0.0d) { jaroslav@559: break; jaroslav@559: } jaroslav@559: if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d jaroslav@559: a[k] = 0.0d; jaroslav@559: a[++p] = -0.0d; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: */ jaroslav@559: private static void doSort(double[] a, int left, int right) { jaroslav@559: // Use Quicksort on small arrays jaroslav@559: if (right - left < QUICKSORT_THRESHOLD) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Index run[i] is the start of i-th run jaroslav@559: * (ascending or descending sequence). jaroslav@559: */ jaroslav@559: int[] run = new int[MAX_RUN_COUNT + 1]; jaroslav@559: int count = 0; run[0] = left; jaroslav@559: jaroslav@559: // Check if the array is nearly sorted jaroslav@559: for (int k = left; k < right; run[count] = k) { jaroslav@559: if (a[k] < a[k + 1]) { // ascending jaroslav@559: while (++k <= right && a[k - 1] <= a[k]); jaroslav@559: } else if (a[k] > a[k + 1]) { // descending jaroslav@559: while (++k <= right && a[k - 1] >= a[k]); jaroslav@559: for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { jaroslav@559: double t = a[lo]; a[lo] = a[hi]; a[hi] = t; jaroslav@559: } jaroslav@559: } else { // equal jaroslav@559: for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) { jaroslav@559: if (--m == 0) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * The array is not highly structured, jaroslav@559: * use Quicksort instead of merge sort. jaroslav@559: */ jaroslav@559: if (++count == MAX_RUN_COUNT) { jaroslav@559: sort(a, left, right, true); jaroslav@559: return; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Check special cases jaroslav@559: if (run[count] == right++) { // The last run contains one element jaroslav@559: run[++count] = right; jaroslav@559: } else if (count == 1) { // The array is already sorted jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Create temporary array, which is used for merging. jaroslav@559: * Implementation note: variable "right" is increased by 1. jaroslav@559: */ jaroslav@559: double[] b; byte odd = 0; jaroslav@559: for (int n = 1; (n <<= 1) < count; odd ^= 1); jaroslav@559: jaroslav@559: if (odd == 0) { jaroslav@559: b = a; a = new double[b.length]; jaroslav@559: for (int i = left - 1; ++i < right; a[i] = b[i]); jaroslav@559: } else { jaroslav@559: b = new double[a.length]; jaroslav@559: } jaroslav@559: jaroslav@559: // Merging jaroslav@559: for (int last; count > 1; count = last) { jaroslav@559: for (int k = (last = 0) + 2; k <= count; k += 2) { jaroslav@559: int hi = run[k], mi = run[k - 1]; jaroslav@559: for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { jaroslav@559: if (q >= hi || p < mi && a[p] <= a[q]) { jaroslav@559: b[i] = a[p++]; jaroslav@559: } else { jaroslav@559: b[i] = a[q++]; jaroslav@559: } jaroslav@559: } jaroslav@559: run[++last] = hi; jaroslav@559: } jaroslav@559: if ((count & 1) != 0) { jaroslav@559: for (int i = right, lo = run[count - 1]; --i >= lo; jaroslav@559: b[i] = a[i] jaroslav@559: ); jaroslav@559: run[++last] = right; jaroslav@559: } jaroslav@559: double[] t = a; a = b; b = t; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /** jaroslav@559: * Sorts the specified range of the array by Dual-Pivot Quicksort. jaroslav@559: * jaroslav@559: * @param a the array to be sorted jaroslav@559: * @param left the index of the first element, inclusive, to be sorted jaroslav@559: * @param right the index of the last element, inclusive, to be sorted jaroslav@559: * @param leftmost indicates if this part is the leftmost in the range jaroslav@559: */ jaroslav@559: private static void sort(double[] a, int left, int right, boolean leftmost) { jaroslav@559: int length = right - left + 1; jaroslav@559: jaroslav@559: // Use insertion sort on tiny arrays jaroslav@559: if (length < INSERTION_SORT_THRESHOLD) { jaroslav@559: if (leftmost) { jaroslav@559: /* jaroslav@559: * Traditional (without sentinel) insertion sort, jaroslav@559: * optimized for server VM, is used in case of jaroslav@559: * the leftmost part. jaroslav@559: */ jaroslav@559: for (int i = left, j = i; i < right; j = ++i) { jaroslav@559: double ai = a[i + 1]; jaroslav@559: while (ai < a[j]) { jaroslav@559: a[j + 1] = a[j]; jaroslav@559: if (j-- == left) { jaroslav@559: break; jaroslav@559: } jaroslav@559: } jaroslav@559: a[j + 1] = ai; jaroslav@559: } jaroslav@559: } else { jaroslav@559: /* jaroslav@559: * Skip the longest ascending sequence. jaroslav@559: */ jaroslav@559: do { jaroslav@559: if (left >= right) { jaroslav@559: return; jaroslav@559: } jaroslav@559: } while (a[++left] >= a[left - 1]); jaroslav@559: jaroslav@559: /* jaroslav@559: * Every element from adjoining part plays the role jaroslav@559: * of sentinel, therefore this allows us to avoid the jaroslav@559: * left range check on each iteration. Moreover, we use jaroslav@559: * the more optimized algorithm, so called pair insertion jaroslav@559: * sort, which is faster (in the context of Quicksort) jaroslav@559: * than traditional implementation of insertion sort. jaroslav@559: */ jaroslav@559: for (int k = left; ++left <= right; k = ++left) { jaroslav@559: double a1 = a[k], a2 = a[left]; jaroslav@559: jaroslav@559: if (a1 < a2) { jaroslav@559: a2 = a1; a1 = a[left]; jaroslav@559: } jaroslav@559: while (a1 < a[--k]) { jaroslav@559: a[k + 2] = a[k]; jaroslav@559: } jaroslav@559: a[++k + 1] = a1; jaroslav@559: jaroslav@559: while (a2 < a[--k]) { jaroslav@559: a[k + 1] = a[k]; jaroslav@559: } jaroslav@559: a[k + 1] = a2; jaroslav@559: } jaroslav@559: double last = a[right]; jaroslav@559: jaroslav@559: while (last < a[--right]) { jaroslav@559: a[right + 1] = a[right]; jaroslav@559: } jaroslav@559: a[right + 1] = last; jaroslav@559: } jaroslav@559: return; jaroslav@559: } jaroslav@559: jaroslav@559: // Inexpensive approximation of length / 7 jaroslav@559: int seventh = (length >> 3) + (length >> 6) + 1; jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort five evenly spaced elements around (and including) the jaroslav@559: * center element in the range. These elements will be used for jaroslav@559: * pivot selection as described below. The choice for spacing jaroslav@559: * these elements was empirically determined to work well on jaroslav@559: * a wide variety of inputs. jaroslav@559: */ jaroslav@559: int e3 = (left + right) >>> 1; // The midpoint jaroslav@559: int e2 = e3 - seventh; jaroslav@559: int e1 = e2 - seventh; jaroslav@559: int e4 = e3 + seventh; jaroslav@559: int e5 = e4 + seventh; jaroslav@559: jaroslav@559: // Sort these elements using insertion sort jaroslav@559: if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; } jaroslav@559: jaroslav@559: if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t; jaroslav@559: if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; jaroslav@559: if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; jaroslav@559: if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Pointers jaroslav@559: int less = left; // The index of the first element of center part jaroslav@559: int great = right; // The index before the first element of right part jaroslav@559: jaroslav@559: if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { jaroslav@559: /* jaroslav@559: * Use the second and fourth of the five sorted elements as pivots. jaroslav@559: * These values are inexpensive approximations of the first and jaroslav@559: * second terciles of the array. Note that pivot1 <= pivot2. jaroslav@559: */ jaroslav@559: double pivot1 = a[e2]; jaroslav@559: double pivot2 = a[e4]; jaroslav@559: jaroslav@559: /* jaroslav@559: * The first and the last elements to be sorted are moved to the jaroslav@559: * locations formerly occupied by the pivots. When partitioning jaroslav@559: * is complete, the pivots are swapped back into their final jaroslav@559: * positions, and excluded from subsequent sorting. jaroslav@559: */ jaroslav@559: a[e2] = a[left]; jaroslav@559: a[e4] = a[right]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Skip elements, which are less or greater than pivot values. jaroslav@559: */ jaroslav@559: while (a[++less] < pivot1); jaroslav@559: while (a[--great] > pivot2); jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | jaroslav@559: * +--------------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot1 jaroslav@559: * pivot1 <= all in [less, k) <= pivot2 jaroslav@559: * all in (great, right) > pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: double ak = a[k]; jaroslav@559: if (ak < pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i++;" instead jaroslav@559: * of "a[i++] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak > pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] > pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] < pivot1) { // a[great] <= pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 <= a[great] <= pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: /* jaroslav@559: * Here and below we use "a[i] = b; i--;" instead jaroslav@559: * of "a[i--] = b;" due to performance issue. jaroslav@559: */ jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Swap pivots into their final positions jaroslav@559: a[left] = a[less - 1]; a[less - 1] = pivot1; jaroslav@559: a[right] = a[great + 1]; a[great + 1] = pivot2; jaroslav@559: jaroslav@559: // Sort left and right parts recursively, excluding known pivots jaroslav@559: sort(a, left, less - 2, leftmost); jaroslav@559: sort(a, great + 2, right, false); jaroslav@559: jaroslav@559: /* jaroslav@559: * If center part is too large (comprises > 4/7 of the array), jaroslav@559: * swap internal pivot values to ends. jaroslav@559: */ jaroslav@559: if (less < e1 && e5 < great) { jaroslav@559: /* jaroslav@559: * Skip elements, which are equal to pivot values. jaroslav@559: */ jaroslav@559: while (a[less] == pivot1) { jaroslav@559: ++less; jaroslav@559: } jaroslav@559: jaroslav@559: while (a[great] == pivot2) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | jaroslav@559: * +----------------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (*, less) == pivot1 jaroslav@559: * pivot1 < all in [less, k) < pivot2 jaroslav@559: * all in (great, *) == pivot2 jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: outer: jaroslav@559: for (int k = less - 1; ++k <= great; ) { jaroslav@559: double ak = a[k]; jaroslav@559: if (ak == pivot1) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else if (ak == pivot2) { // Move a[k] to right part jaroslav@559: while (a[great] == pivot2) { jaroslav@559: if (great-- == k) { jaroslav@559: break outer; jaroslav@559: } jaroslav@559: } jaroslav@559: if (a[great] == pivot1) { // a[great] < pivot2 jaroslav@559: a[k] = a[less]; jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot1, the jaroslav@559: * assignment a[less] = pivot1 may be incorrect, jaroslav@559: * if a[great] and pivot1 are floating-point zeros jaroslav@559: * of different signs. Therefore in float and jaroslav@559: * double sorting methods we have to use more jaroslav@559: * accurate assignment a[less] = a[great]. jaroslav@559: */ jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // pivot1 < a[great] < pivot2 jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: // Sort center part recursively jaroslav@559: sort(a, less, great, false); jaroslav@559: jaroslav@559: } else { // Partitioning with one pivot jaroslav@559: /* jaroslav@559: * Use the third of the five sorted elements as pivot. jaroslav@559: * This value is inexpensive approximation of the median. jaroslav@559: */ jaroslav@559: double pivot = a[e3]; jaroslav@559: jaroslav@559: /* jaroslav@559: * Partitioning degenerates to the traditional 3-way jaroslav@559: * (or "Dutch National Flag") schema: jaroslav@559: * jaroslav@559: * left part center part right part jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * | < pivot | == pivot | ? | > pivot | jaroslav@559: * +-------------------------------------------------+ jaroslav@559: * ^ ^ ^ jaroslav@559: * | | | jaroslav@559: * less k great jaroslav@559: * jaroslav@559: * Invariants: jaroslav@559: * jaroslav@559: * all in (left, less) < pivot jaroslav@559: * all in [less, k) == pivot jaroslav@559: * all in (great, right) > pivot jaroslav@559: * jaroslav@559: * Pointer k is the first index of ?-part. jaroslav@559: */ jaroslav@559: for (int k = less; k <= great; ++k) { jaroslav@559: if (a[k] == pivot) { jaroslav@559: continue; jaroslav@559: } jaroslav@559: double ak = a[k]; jaroslav@559: if (ak < pivot) { // Move a[k] to left part jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = ak; jaroslav@559: ++less; jaroslav@559: } else { // a[k] > pivot - Move a[k] to right part jaroslav@559: while (a[great] > pivot) { jaroslav@559: --great; jaroslav@559: } jaroslav@559: if (a[great] < pivot) { // a[great] <= pivot jaroslav@559: a[k] = a[less]; jaroslav@559: a[less] = a[great]; jaroslav@559: ++less; jaroslav@559: } else { // a[great] == pivot jaroslav@559: /* jaroslav@559: * Even though a[great] equals to pivot, the jaroslav@559: * assignment a[k] = pivot may be incorrect, jaroslav@559: * if a[great] and pivot are floating-point jaroslav@559: * zeros of different signs. Therefore in float jaroslav@559: * and double sorting methods we have to use jaroslav@559: * more accurate assignment a[k] = a[great]. jaroslav@559: */ jaroslav@559: a[k] = a[great]; jaroslav@559: } jaroslav@559: a[great] = ak; jaroslav@559: --great; jaroslav@559: } jaroslav@559: } jaroslav@559: jaroslav@559: /* jaroslav@559: * Sort left and right parts recursively. jaroslav@559: * All elements from center part are equal jaroslav@559: * and, therefore, already sorted. jaroslav@559: */ jaroslav@559: sort(a, left, less - 1, leftmost); jaroslav@559: sort(a, great + 1, right, false); jaroslav@559: } jaroslav@559: } jaroslav@559: }