1.1 --- a/emul/compact/src/main/java/java/util/DualPivotQuicksort.java Tue Feb 26 14:55:55 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,3018 +0,0 @@
1.4 -/*
1.5 - * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 - *
1.8 - * This code is free software; you can redistribute it and/or modify it
1.9 - * under the terms of the GNU General Public License version 2 only, as
1.10 - * published by the Free Software Foundation. Oracle designates this
1.11 - * particular file as subject to the "Classpath" exception as provided
1.12 - * by Oracle in the LICENSE file that accompanied this code.
1.13 - *
1.14 - * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 - * version 2 for more details (a copy is included in the LICENSE file that
1.18 - * accompanied this code).
1.19 - *
1.20 - * You should have received a copy of the GNU General Public License version
1.21 - * 2 along with this work; if not, write to the Free Software Foundation,
1.22 - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 - *
1.24 - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 - * or visit www.oracle.com if you need additional information or have any
1.26 - * questions.
1.27 - */
1.28 -
1.29 -package java.util;
1.30 -
1.31 -/**
1.32 - * This class implements the Dual-Pivot Quicksort algorithm by
1.33 - * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
1.34 - * offers O(n log(n)) performance on many data sets that cause other
1.35 - * quicksorts to degrade to quadratic performance, and is typically
1.36 - * faster than traditional (one-pivot) Quicksort implementations.
1.37 - *
1.38 - * @author Vladimir Yaroslavskiy
1.39 - * @author Jon Bentley
1.40 - * @author Josh Bloch
1.41 - *
1.42 - * @version 2011.02.11 m765.827.12i:5\7pm
1.43 - * @since 1.7
1.44 - */
1.45 -final class DualPivotQuicksort {
1.46 -
1.47 - /**
1.48 - * Prevents instantiation.
1.49 - */
1.50 - private DualPivotQuicksort() {}
1.51 -
1.52 - /*
1.53 - * Tuning parameters.
1.54 - */
1.55 -
1.56 - /**
1.57 - * The maximum number of runs in merge sort.
1.58 - */
1.59 - private static final int MAX_RUN_COUNT = 67;
1.60 -
1.61 - /**
1.62 - * The maximum length of run in merge sort.
1.63 - */
1.64 - private static final int MAX_RUN_LENGTH = 33;
1.65 -
1.66 - /**
1.67 - * If the length of an array to be sorted is less than this
1.68 - * constant, Quicksort is used in preference to merge sort.
1.69 - */
1.70 - private static final int QUICKSORT_THRESHOLD = 286;
1.71 -
1.72 - /**
1.73 - * If the length of an array to be sorted is less than this
1.74 - * constant, insertion sort is used in preference to Quicksort.
1.75 - */
1.76 - private static final int INSERTION_SORT_THRESHOLD = 47;
1.77 -
1.78 - /**
1.79 - * If the length of a byte array to be sorted is greater than this
1.80 - * constant, counting sort is used in preference to insertion sort.
1.81 - */
1.82 - private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
1.83 -
1.84 - /**
1.85 - * If the length of a short or char array to be sorted is greater
1.86 - * than this constant, counting sort is used in preference to Quicksort.
1.87 - */
1.88 - private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
1.89 -
1.90 - /*
1.91 - * Sorting methods for seven primitive types.
1.92 - */
1.93 -
1.94 - /**
1.95 - * Sorts the specified array.
1.96 - *
1.97 - * @param a the array to be sorted
1.98 - */
1.99 - public static void sort(int[] a) {
1.100 - sort(a, 0, a.length - 1);
1.101 - }
1.102 -
1.103 - /**
1.104 - * Sorts the specified range of the array.
1.105 - *
1.106 - * @param a the array to be sorted
1.107 - * @param left the index of the first element, inclusive, to be sorted
1.108 - * @param right the index of the last element, inclusive, to be sorted
1.109 - */
1.110 - public static void sort(int[] a, int left, int right) {
1.111 - // Use Quicksort on small arrays
1.112 - if (right - left < QUICKSORT_THRESHOLD) {
1.113 - sort(a, left, right, true);
1.114 - return;
1.115 - }
1.116 -
1.117 - /*
1.118 - * Index run[i] is the start of i-th run
1.119 - * (ascending or descending sequence).
1.120 - */
1.121 - int[] run = new int[MAX_RUN_COUNT + 1];
1.122 - int count = 0; run[0] = left;
1.123 -
1.124 - // Check if the array is nearly sorted
1.125 - for (int k = left; k < right; run[count] = k) {
1.126 - if (a[k] < a[k + 1]) { // ascending
1.127 - while (++k <= right && a[k - 1] <= a[k]);
1.128 - } else if (a[k] > a[k + 1]) { // descending
1.129 - while (++k <= right && a[k - 1] >= a[k]);
1.130 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.131 - int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.132 - }
1.133 - } else { // equal
1.134 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.135 - if (--m == 0) {
1.136 - sort(a, left, right, true);
1.137 - return;
1.138 - }
1.139 - }
1.140 - }
1.141 -
1.142 - /*
1.143 - * The array is not highly structured,
1.144 - * use Quicksort instead of merge sort.
1.145 - */
1.146 - if (++count == MAX_RUN_COUNT) {
1.147 - sort(a, left, right, true);
1.148 - return;
1.149 - }
1.150 - }
1.151 -
1.152 - // Check special cases
1.153 - if (run[count] == right++) { // The last run contains one element
1.154 - run[++count] = right;
1.155 - } else if (count == 1) { // The array is already sorted
1.156 - return;
1.157 - }
1.158 -
1.159 - /*
1.160 - * Create temporary array, which is used for merging.
1.161 - * Implementation note: variable "right" is increased by 1.
1.162 - */
1.163 - int[] b; byte odd = 0;
1.164 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.165 -
1.166 - if (odd == 0) {
1.167 - b = a; a = new int[b.length];
1.168 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.169 - } else {
1.170 - b = new int[a.length];
1.171 - }
1.172 -
1.173 - // Merging
1.174 - for (int last; count > 1; count = last) {
1.175 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.176 - int hi = run[k], mi = run[k - 1];
1.177 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.178 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.179 - b[i] = a[p++];
1.180 - } else {
1.181 - b[i] = a[q++];
1.182 - }
1.183 - }
1.184 - run[++last] = hi;
1.185 - }
1.186 - if ((count & 1) != 0) {
1.187 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.188 - b[i] = a[i]
1.189 - );
1.190 - run[++last] = right;
1.191 - }
1.192 - int[] t = a; a = b; b = t;
1.193 - }
1.194 - }
1.195 -
1.196 - /**
1.197 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.198 - *
1.199 - * @param a the array to be sorted
1.200 - * @param left the index of the first element, inclusive, to be sorted
1.201 - * @param right the index of the last element, inclusive, to be sorted
1.202 - * @param leftmost indicates if this part is the leftmost in the range
1.203 - */
1.204 - private static void sort(int[] a, int left, int right, boolean leftmost) {
1.205 - int length = right - left + 1;
1.206 -
1.207 - // Use insertion sort on tiny arrays
1.208 - if (length < INSERTION_SORT_THRESHOLD) {
1.209 - if (leftmost) {
1.210 - /*
1.211 - * Traditional (without sentinel) insertion sort,
1.212 - * optimized for server VM, is used in case of
1.213 - * the leftmost part.
1.214 - */
1.215 - for (int i = left, j = i; i < right; j = ++i) {
1.216 - int ai = a[i + 1];
1.217 - while (ai < a[j]) {
1.218 - a[j + 1] = a[j];
1.219 - if (j-- == left) {
1.220 - break;
1.221 - }
1.222 - }
1.223 - a[j + 1] = ai;
1.224 - }
1.225 - } else {
1.226 - /*
1.227 - * Skip the longest ascending sequence.
1.228 - */
1.229 - do {
1.230 - if (left >= right) {
1.231 - return;
1.232 - }
1.233 - } while (a[++left] >= a[left - 1]);
1.234 -
1.235 - /*
1.236 - * Every element from adjoining part plays the role
1.237 - * of sentinel, therefore this allows us to avoid the
1.238 - * left range check on each iteration. Moreover, we use
1.239 - * the more optimized algorithm, so called pair insertion
1.240 - * sort, which is faster (in the context of Quicksort)
1.241 - * than traditional implementation of insertion sort.
1.242 - */
1.243 - for (int k = left; ++left <= right; k = ++left) {
1.244 - int a1 = a[k], a2 = a[left];
1.245 -
1.246 - if (a1 < a2) {
1.247 - a2 = a1; a1 = a[left];
1.248 - }
1.249 - while (a1 < a[--k]) {
1.250 - a[k + 2] = a[k];
1.251 - }
1.252 - a[++k + 1] = a1;
1.253 -
1.254 - while (a2 < a[--k]) {
1.255 - a[k + 1] = a[k];
1.256 - }
1.257 - a[k + 1] = a2;
1.258 - }
1.259 - int last = a[right];
1.260 -
1.261 - while (last < a[--right]) {
1.262 - a[right + 1] = a[right];
1.263 - }
1.264 - a[right + 1] = last;
1.265 - }
1.266 - return;
1.267 - }
1.268 -
1.269 - // Inexpensive approximation of length / 7
1.270 - int seventh = (length >> 3) + (length >> 6) + 1;
1.271 -
1.272 - /*
1.273 - * Sort five evenly spaced elements around (and including) the
1.274 - * center element in the range. These elements will be used for
1.275 - * pivot selection as described below. The choice for spacing
1.276 - * these elements was empirically determined to work well on
1.277 - * a wide variety of inputs.
1.278 - */
1.279 - int e3 = (left + right) >>> 1; // The midpoint
1.280 - int e2 = e3 - seventh;
1.281 - int e1 = e2 - seventh;
1.282 - int e4 = e3 + seventh;
1.283 - int e5 = e4 + seventh;
1.284 -
1.285 - // Sort these elements using insertion sort
1.286 - if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.287 -
1.288 - if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.289 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.290 - }
1.291 - if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.292 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.293 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.294 - }
1.295 - }
1.296 - if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.297 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.298 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.299 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.300 - }
1.301 - }
1.302 - }
1.303 -
1.304 - // Pointers
1.305 - int less = left; // The index of the first element of center part
1.306 - int great = right; // The index before the first element of right part
1.307 -
1.308 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.309 - /*
1.310 - * Use the second and fourth of the five sorted elements as pivots.
1.311 - * These values are inexpensive approximations of the first and
1.312 - * second terciles of the array. Note that pivot1 <= pivot2.
1.313 - */
1.314 - int pivot1 = a[e2];
1.315 - int pivot2 = a[e4];
1.316 -
1.317 - /*
1.318 - * The first and the last elements to be sorted are moved to the
1.319 - * locations formerly occupied by the pivots. When partitioning
1.320 - * is complete, the pivots are swapped back into their final
1.321 - * positions, and excluded from subsequent sorting.
1.322 - */
1.323 - a[e2] = a[left];
1.324 - a[e4] = a[right];
1.325 -
1.326 - /*
1.327 - * Skip elements, which are less or greater than pivot values.
1.328 - */
1.329 - while (a[++less] < pivot1);
1.330 - while (a[--great] > pivot2);
1.331 -
1.332 - /*
1.333 - * Partitioning:
1.334 - *
1.335 - * left part center part right part
1.336 - * +--------------------------------------------------------------+
1.337 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.338 - * +--------------------------------------------------------------+
1.339 - * ^ ^ ^
1.340 - * | | |
1.341 - * less k great
1.342 - *
1.343 - * Invariants:
1.344 - *
1.345 - * all in (left, less) < pivot1
1.346 - * pivot1 <= all in [less, k) <= pivot2
1.347 - * all in (great, right) > pivot2
1.348 - *
1.349 - * Pointer k is the first index of ?-part.
1.350 - */
1.351 - outer:
1.352 - for (int k = less - 1; ++k <= great; ) {
1.353 - int ak = a[k];
1.354 - if (ak < pivot1) { // Move a[k] to left part
1.355 - a[k] = a[less];
1.356 - /*
1.357 - * Here and below we use "a[i] = b; i++;" instead
1.358 - * of "a[i++] = b;" due to performance issue.
1.359 - */
1.360 - a[less] = ak;
1.361 - ++less;
1.362 - } else if (ak > pivot2) { // Move a[k] to right part
1.363 - while (a[great] > pivot2) {
1.364 - if (great-- == k) {
1.365 - break outer;
1.366 - }
1.367 - }
1.368 - if (a[great] < pivot1) { // a[great] <= pivot2
1.369 - a[k] = a[less];
1.370 - a[less] = a[great];
1.371 - ++less;
1.372 - } else { // pivot1 <= a[great] <= pivot2
1.373 - a[k] = a[great];
1.374 - }
1.375 - /*
1.376 - * Here and below we use "a[i] = b; i--;" instead
1.377 - * of "a[i--] = b;" due to performance issue.
1.378 - */
1.379 - a[great] = ak;
1.380 - --great;
1.381 - }
1.382 - }
1.383 -
1.384 - // Swap pivots into their final positions
1.385 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.386 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.387 -
1.388 - // Sort left and right parts recursively, excluding known pivots
1.389 - sort(a, left, less - 2, leftmost);
1.390 - sort(a, great + 2, right, false);
1.391 -
1.392 - /*
1.393 - * If center part is too large (comprises > 4/7 of the array),
1.394 - * swap internal pivot values to ends.
1.395 - */
1.396 - if (less < e1 && e5 < great) {
1.397 - /*
1.398 - * Skip elements, which are equal to pivot values.
1.399 - */
1.400 - while (a[less] == pivot1) {
1.401 - ++less;
1.402 - }
1.403 -
1.404 - while (a[great] == pivot2) {
1.405 - --great;
1.406 - }
1.407 -
1.408 - /*
1.409 - * Partitioning:
1.410 - *
1.411 - * left part center part right part
1.412 - * +----------------------------------------------------------+
1.413 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.414 - * +----------------------------------------------------------+
1.415 - * ^ ^ ^
1.416 - * | | |
1.417 - * less k great
1.418 - *
1.419 - * Invariants:
1.420 - *
1.421 - * all in (*, less) == pivot1
1.422 - * pivot1 < all in [less, k) < pivot2
1.423 - * all in (great, *) == pivot2
1.424 - *
1.425 - * Pointer k is the first index of ?-part.
1.426 - */
1.427 - outer:
1.428 - for (int k = less - 1; ++k <= great; ) {
1.429 - int ak = a[k];
1.430 - if (ak == pivot1) { // Move a[k] to left part
1.431 - a[k] = a[less];
1.432 - a[less] = ak;
1.433 - ++less;
1.434 - } else if (ak == pivot2) { // Move a[k] to right part
1.435 - while (a[great] == pivot2) {
1.436 - if (great-- == k) {
1.437 - break outer;
1.438 - }
1.439 - }
1.440 - if (a[great] == pivot1) { // a[great] < pivot2
1.441 - a[k] = a[less];
1.442 - /*
1.443 - * Even though a[great] equals to pivot1, the
1.444 - * assignment a[less] = pivot1 may be incorrect,
1.445 - * if a[great] and pivot1 are floating-point zeros
1.446 - * of different signs. Therefore in float and
1.447 - * double sorting methods we have to use more
1.448 - * accurate assignment a[less] = a[great].
1.449 - */
1.450 - a[less] = pivot1;
1.451 - ++less;
1.452 - } else { // pivot1 < a[great] < pivot2
1.453 - a[k] = a[great];
1.454 - }
1.455 - a[great] = ak;
1.456 - --great;
1.457 - }
1.458 - }
1.459 - }
1.460 -
1.461 - // Sort center part recursively
1.462 - sort(a, less, great, false);
1.463 -
1.464 - } else { // Partitioning with one pivot
1.465 - /*
1.466 - * Use the third of the five sorted elements as pivot.
1.467 - * This value is inexpensive approximation of the median.
1.468 - */
1.469 - int pivot = a[e3];
1.470 -
1.471 - /*
1.472 - * Partitioning degenerates to the traditional 3-way
1.473 - * (or "Dutch National Flag") schema:
1.474 - *
1.475 - * left part center part right part
1.476 - * +-------------------------------------------------+
1.477 - * | < pivot | == pivot | ? | > pivot |
1.478 - * +-------------------------------------------------+
1.479 - * ^ ^ ^
1.480 - * | | |
1.481 - * less k great
1.482 - *
1.483 - * Invariants:
1.484 - *
1.485 - * all in (left, less) < pivot
1.486 - * all in [less, k) == pivot
1.487 - * all in (great, right) > pivot
1.488 - *
1.489 - * Pointer k is the first index of ?-part.
1.490 - */
1.491 - for (int k = less; k <= great; ++k) {
1.492 - if (a[k] == pivot) {
1.493 - continue;
1.494 - }
1.495 - int ak = a[k];
1.496 - if (ak < pivot) { // Move a[k] to left part
1.497 - a[k] = a[less];
1.498 - a[less] = ak;
1.499 - ++less;
1.500 - } else { // a[k] > pivot - Move a[k] to right part
1.501 - while (a[great] > pivot) {
1.502 - --great;
1.503 - }
1.504 - if (a[great] < pivot) { // a[great] <= pivot
1.505 - a[k] = a[less];
1.506 - a[less] = a[great];
1.507 - ++less;
1.508 - } else { // a[great] == pivot
1.509 - /*
1.510 - * Even though a[great] equals to pivot, the
1.511 - * assignment a[k] = pivot may be incorrect,
1.512 - * if a[great] and pivot are floating-point
1.513 - * zeros of different signs. Therefore in float
1.514 - * and double sorting methods we have to use
1.515 - * more accurate assignment a[k] = a[great].
1.516 - */
1.517 - a[k] = pivot;
1.518 - }
1.519 - a[great] = ak;
1.520 - --great;
1.521 - }
1.522 - }
1.523 -
1.524 - /*
1.525 - * Sort left and right parts recursively.
1.526 - * All elements from center part are equal
1.527 - * and, therefore, already sorted.
1.528 - */
1.529 - sort(a, left, less - 1, leftmost);
1.530 - sort(a, great + 1, right, false);
1.531 - }
1.532 - }
1.533 -
1.534 - /**
1.535 - * Sorts the specified array.
1.536 - *
1.537 - * @param a the array to be sorted
1.538 - */
1.539 - public static void sort(long[] a) {
1.540 - sort(a, 0, a.length - 1);
1.541 - }
1.542 -
1.543 - /**
1.544 - * Sorts the specified range of the array.
1.545 - *
1.546 - * @param a the array to be sorted
1.547 - * @param left the index of the first element, inclusive, to be sorted
1.548 - * @param right the index of the last element, inclusive, to be sorted
1.549 - */
1.550 - public static void sort(long[] a, int left, int right) {
1.551 - // Use Quicksort on small arrays
1.552 - if (right - left < QUICKSORT_THRESHOLD) {
1.553 - sort(a, left, right, true);
1.554 - return;
1.555 - }
1.556 -
1.557 - /*
1.558 - * Index run[i] is the start of i-th run
1.559 - * (ascending or descending sequence).
1.560 - */
1.561 - int[] run = new int[MAX_RUN_COUNT + 1];
1.562 - int count = 0; run[0] = left;
1.563 -
1.564 - // Check if the array is nearly sorted
1.565 - for (int k = left; k < right; run[count] = k) {
1.566 - if (a[k] < a[k + 1]) { // ascending
1.567 - while (++k <= right && a[k - 1] <= a[k]);
1.568 - } else if (a[k] > a[k + 1]) { // descending
1.569 - while (++k <= right && a[k - 1] >= a[k]);
1.570 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.571 - long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.572 - }
1.573 - } else { // equal
1.574 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.575 - if (--m == 0) {
1.576 - sort(a, left, right, true);
1.577 - return;
1.578 - }
1.579 - }
1.580 - }
1.581 -
1.582 - /*
1.583 - * The array is not highly structured,
1.584 - * use Quicksort instead of merge sort.
1.585 - */
1.586 - if (++count == MAX_RUN_COUNT) {
1.587 - sort(a, left, right, true);
1.588 - return;
1.589 - }
1.590 - }
1.591 -
1.592 - // Check special cases
1.593 - if (run[count] == right++) { // The last run contains one element
1.594 - run[++count] = right;
1.595 - } else if (count == 1) { // The array is already sorted
1.596 - return;
1.597 - }
1.598 -
1.599 - /*
1.600 - * Create temporary array, which is used for merging.
1.601 - * Implementation note: variable "right" is increased by 1.
1.602 - */
1.603 - long[] b; byte odd = 0;
1.604 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.605 -
1.606 - if (odd == 0) {
1.607 - b = a; a = new long[b.length];
1.608 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.609 - } else {
1.610 - b = new long[a.length];
1.611 - }
1.612 -
1.613 - // Merging
1.614 - for (int last; count > 1; count = last) {
1.615 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.616 - int hi = run[k], mi = run[k - 1];
1.617 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.618 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.619 - b[i] = a[p++];
1.620 - } else {
1.621 - b[i] = a[q++];
1.622 - }
1.623 - }
1.624 - run[++last] = hi;
1.625 - }
1.626 - if ((count & 1) != 0) {
1.627 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.628 - b[i] = a[i]
1.629 - );
1.630 - run[++last] = right;
1.631 - }
1.632 - long[] t = a; a = b; b = t;
1.633 - }
1.634 - }
1.635 -
1.636 - /**
1.637 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.638 - *
1.639 - * @param a the array to be sorted
1.640 - * @param left the index of the first element, inclusive, to be sorted
1.641 - * @param right the index of the last element, inclusive, to be sorted
1.642 - * @param leftmost indicates if this part is the leftmost in the range
1.643 - */
1.644 - private static void sort(long[] a, int left, int right, boolean leftmost) {
1.645 - int length = right - left + 1;
1.646 -
1.647 - // Use insertion sort on tiny arrays
1.648 - if (length < INSERTION_SORT_THRESHOLD) {
1.649 - if (leftmost) {
1.650 - /*
1.651 - * Traditional (without sentinel) insertion sort,
1.652 - * optimized for server VM, is used in case of
1.653 - * the leftmost part.
1.654 - */
1.655 - for (int i = left, j = i; i < right; j = ++i) {
1.656 - long ai = a[i + 1];
1.657 - while (ai < a[j]) {
1.658 - a[j + 1] = a[j];
1.659 - if (j-- == left) {
1.660 - break;
1.661 - }
1.662 - }
1.663 - a[j + 1] = ai;
1.664 - }
1.665 - } else {
1.666 - /*
1.667 - * Skip the longest ascending sequence.
1.668 - */
1.669 - do {
1.670 - if (left >= right) {
1.671 - return;
1.672 - }
1.673 - } while (a[++left] >= a[left - 1]);
1.674 -
1.675 - /*
1.676 - * Every element from adjoining part plays the role
1.677 - * of sentinel, therefore this allows us to avoid the
1.678 - * left range check on each iteration. Moreover, we use
1.679 - * the more optimized algorithm, so called pair insertion
1.680 - * sort, which is faster (in the context of Quicksort)
1.681 - * than traditional implementation of insertion sort.
1.682 - */
1.683 - for (int k = left; ++left <= right; k = ++left) {
1.684 - long a1 = a[k], a2 = a[left];
1.685 -
1.686 - if (a1 < a2) {
1.687 - a2 = a1; a1 = a[left];
1.688 - }
1.689 - while (a1 < a[--k]) {
1.690 - a[k + 2] = a[k];
1.691 - }
1.692 - a[++k + 1] = a1;
1.693 -
1.694 - while (a2 < a[--k]) {
1.695 - a[k + 1] = a[k];
1.696 - }
1.697 - a[k + 1] = a2;
1.698 - }
1.699 - long last = a[right];
1.700 -
1.701 - while (last < a[--right]) {
1.702 - a[right + 1] = a[right];
1.703 - }
1.704 - a[right + 1] = last;
1.705 - }
1.706 - return;
1.707 - }
1.708 -
1.709 - // Inexpensive approximation of length / 7
1.710 - int seventh = (length >> 3) + (length >> 6) + 1;
1.711 -
1.712 - /*
1.713 - * Sort five evenly spaced elements around (and including) the
1.714 - * center element in the range. These elements will be used for
1.715 - * pivot selection as described below. The choice for spacing
1.716 - * these elements was empirically determined to work well on
1.717 - * a wide variety of inputs.
1.718 - */
1.719 - int e3 = (left + right) >>> 1; // The midpoint
1.720 - int e2 = e3 - seventh;
1.721 - int e1 = e2 - seventh;
1.722 - int e4 = e3 + seventh;
1.723 - int e5 = e4 + seventh;
1.724 -
1.725 - // Sort these elements using insertion sort
1.726 - if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.727 -
1.728 - if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.729 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.730 - }
1.731 - if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.732 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.733 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.734 - }
1.735 - }
1.736 - if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.737 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.738 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.739 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.740 - }
1.741 - }
1.742 - }
1.743 -
1.744 - // Pointers
1.745 - int less = left; // The index of the first element of center part
1.746 - int great = right; // The index before the first element of right part
1.747 -
1.748 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.749 - /*
1.750 - * Use the second and fourth of the five sorted elements as pivots.
1.751 - * These values are inexpensive approximations of the first and
1.752 - * second terciles of the array. Note that pivot1 <= pivot2.
1.753 - */
1.754 - long pivot1 = a[e2];
1.755 - long pivot2 = a[e4];
1.756 -
1.757 - /*
1.758 - * The first and the last elements to be sorted are moved to the
1.759 - * locations formerly occupied by the pivots. When partitioning
1.760 - * is complete, the pivots are swapped back into their final
1.761 - * positions, and excluded from subsequent sorting.
1.762 - */
1.763 - a[e2] = a[left];
1.764 - a[e4] = a[right];
1.765 -
1.766 - /*
1.767 - * Skip elements, which are less or greater than pivot values.
1.768 - */
1.769 - while (a[++less] < pivot1);
1.770 - while (a[--great] > pivot2);
1.771 -
1.772 - /*
1.773 - * Partitioning:
1.774 - *
1.775 - * left part center part right part
1.776 - * +--------------------------------------------------------------+
1.777 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.778 - * +--------------------------------------------------------------+
1.779 - * ^ ^ ^
1.780 - * | | |
1.781 - * less k great
1.782 - *
1.783 - * Invariants:
1.784 - *
1.785 - * all in (left, less) < pivot1
1.786 - * pivot1 <= all in [less, k) <= pivot2
1.787 - * all in (great, right) > pivot2
1.788 - *
1.789 - * Pointer k is the first index of ?-part.
1.790 - */
1.791 - outer:
1.792 - for (int k = less - 1; ++k <= great; ) {
1.793 - long ak = a[k];
1.794 - if (ak < pivot1) { // Move a[k] to left part
1.795 - a[k] = a[less];
1.796 - /*
1.797 - * Here and below we use "a[i] = b; i++;" instead
1.798 - * of "a[i++] = b;" due to performance issue.
1.799 - */
1.800 - a[less] = ak;
1.801 - ++less;
1.802 - } else if (ak > pivot2) { // Move a[k] to right part
1.803 - while (a[great] > pivot2) {
1.804 - if (great-- == k) {
1.805 - break outer;
1.806 - }
1.807 - }
1.808 - if (a[great] < pivot1) { // a[great] <= pivot2
1.809 - a[k] = a[less];
1.810 - a[less] = a[great];
1.811 - ++less;
1.812 - } else { // pivot1 <= a[great] <= pivot2
1.813 - a[k] = a[great];
1.814 - }
1.815 - /*
1.816 - * Here and below we use "a[i] = b; i--;" instead
1.817 - * of "a[i--] = b;" due to performance issue.
1.818 - */
1.819 - a[great] = ak;
1.820 - --great;
1.821 - }
1.822 - }
1.823 -
1.824 - // Swap pivots into their final positions
1.825 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.826 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.827 -
1.828 - // Sort left and right parts recursively, excluding known pivots
1.829 - sort(a, left, less - 2, leftmost);
1.830 - sort(a, great + 2, right, false);
1.831 -
1.832 - /*
1.833 - * If center part is too large (comprises > 4/7 of the array),
1.834 - * swap internal pivot values to ends.
1.835 - */
1.836 - if (less < e1 && e5 < great) {
1.837 - /*
1.838 - * Skip elements, which are equal to pivot values.
1.839 - */
1.840 - while (a[less] == pivot1) {
1.841 - ++less;
1.842 - }
1.843 -
1.844 - while (a[great] == pivot2) {
1.845 - --great;
1.846 - }
1.847 -
1.848 - /*
1.849 - * Partitioning:
1.850 - *
1.851 - * left part center part right part
1.852 - * +----------------------------------------------------------+
1.853 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.854 - * +----------------------------------------------------------+
1.855 - * ^ ^ ^
1.856 - * | | |
1.857 - * less k great
1.858 - *
1.859 - * Invariants:
1.860 - *
1.861 - * all in (*, less) == pivot1
1.862 - * pivot1 < all in [less, k) < pivot2
1.863 - * all in (great, *) == pivot2
1.864 - *
1.865 - * Pointer k is the first index of ?-part.
1.866 - */
1.867 - outer:
1.868 - for (int k = less - 1; ++k <= great; ) {
1.869 - long ak = a[k];
1.870 - if (ak == pivot1) { // Move a[k] to left part
1.871 - a[k] = a[less];
1.872 - a[less] = ak;
1.873 - ++less;
1.874 - } else if (ak == pivot2) { // Move a[k] to right part
1.875 - while (a[great] == pivot2) {
1.876 - if (great-- == k) {
1.877 - break outer;
1.878 - }
1.879 - }
1.880 - if (a[great] == pivot1) { // a[great] < pivot2
1.881 - a[k] = a[less];
1.882 - /*
1.883 - * Even though a[great] equals to pivot1, the
1.884 - * assignment a[less] = pivot1 may be incorrect,
1.885 - * if a[great] and pivot1 are floating-point zeros
1.886 - * of different signs. Therefore in float and
1.887 - * double sorting methods we have to use more
1.888 - * accurate assignment a[less] = a[great].
1.889 - */
1.890 - a[less] = pivot1;
1.891 - ++less;
1.892 - } else { // pivot1 < a[great] < pivot2
1.893 - a[k] = a[great];
1.894 - }
1.895 - a[great] = ak;
1.896 - --great;
1.897 - }
1.898 - }
1.899 - }
1.900 -
1.901 - // Sort center part recursively
1.902 - sort(a, less, great, false);
1.903 -
1.904 - } else { // Partitioning with one pivot
1.905 - /*
1.906 - * Use the third of the five sorted elements as pivot.
1.907 - * This value is inexpensive approximation of the median.
1.908 - */
1.909 - long pivot = a[e3];
1.910 -
1.911 - /*
1.912 - * Partitioning degenerates to the traditional 3-way
1.913 - * (or "Dutch National Flag") schema:
1.914 - *
1.915 - * left part center part right part
1.916 - * +-------------------------------------------------+
1.917 - * | < pivot | == pivot | ? | > pivot |
1.918 - * +-------------------------------------------------+
1.919 - * ^ ^ ^
1.920 - * | | |
1.921 - * less k great
1.922 - *
1.923 - * Invariants:
1.924 - *
1.925 - * all in (left, less) < pivot
1.926 - * all in [less, k) == pivot
1.927 - * all in (great, right) > pivot
1.928 - *
1.929 - * Pointer k is the first index of ?-part.
1.930 - */
1.931 - for (int k = less; k <= great; ++k) {
1.932 - if (a[k] == pivot) {
1.933 - continue;
1.934 - }
1.935 - long ak = a[k];
1.936 - if (ak < pivot) { // Move a[k] to left part
1.937 - a[k] = a[less];
1.938 - a[less] = ak;
1.939 - ++less;
1.940 - } else { // a[k] > pivot - Move a[k] to right part
1.941 - while (a[great] > pivot) {
1.942 - --great;
1.943 - }
1.944 - if (a[great] < pivot) { // a[great] <= pivot
1.945 - a[k] = a[less];
1.946 - a[less] = a[great];
1.947 - ++less;
1.948 - } else { // a[great] == pivot
1.949 - /*
1.950 - * Even though a[great] equals to pivot, the
1.951 - * assignment a[k] = pivot may be incorrect,
1.952 - * if a[great] and pivot are floating-point
1.953 - * zeros of different signs. Therefore in float
1.954 - * and double sorting methods we have to use
1.955 - * more accurate assignment a[k] = a[great].
1.956 - */
1.957 - a[k] = pivot;
1.958 - }
1.959 - a[great] = ak;
1.960 - --great;
1.961 - }
1.962 - }
1.963 -
1.964 - /*
1.965 - * Sort left and right parts recursively.
1.966 - * All elements from center part are equal
1.967 - * and, therefore, already sorted.
1.968 - */
1.969 - sort(a, left, less - 1, leftmost);
1.970 - sort(a, great + 1, right, false);
1.971 - }
1.972 - }
1.973 -
1.974 - /**
1.975 - * Sorts the specified array.
1.976 - *
1.977 - * @param a the array to be sorted
1.978 - */
1.979 - public static void sort(short[] a) {
1.980 - sort(a, 0, a.length - 1);
1.981 - }
1.982 -
1.983 - /**
1.984 - * Sorts the specified range of the array.
1.985 - *
1.986 - * @param a the array to be sorted
1.987 - * @param left the index of the first element, inclusive, to be sorted
1.988 - * @param right the index of the last element, inclusive, to be sorted
1.989 - */
1.990 - public static void sort(short[] a, int left, int right) {
1.991 - // Use counting sort on large arrays
1.992 - if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
1.993 - int[] count = new int[NUM_SHORT_VALUES];
1.994 -
1.995 - for (int i = left - 1; ++i <= right;
1.996 - count[a[i] - Short.MIN_VALUE]++
1.997 - );
1.998 - for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
1.999 - while (count[--i] == 0);
1.1000 - short value = (short) (i + Short.MIN_VALUE);
1.1001 - int s = count[i];
1.1002 -
1.1003 - do {
1.1004 - a[--k] = value;
1.1005 - } while (--s > 0);
1.1006 - }
1.1007 - } else { // Use Dual-Pivot Quicksort on small arrays
1.1008 - doSort(a, left, right);
1.1009 - }
1.1010 - }
1.1011 -
1.1012 - /** The number of distinct short values. */
1.1013 - private static final int NUM_SHORT_VALUES = 1 << 16;
1.1014 -
1.1015 - /**
1.1016 - * Sorts the specified range of the array.
1.1017 - *
1.1018 - * @param a the array to be sorted
1.1019 - * @param left the index of the first element, inclusive, to be sorted
1.1020 - * @param right the index of the last element, inclusive, to be sorted
1.1021 - */
1.1022 - private static void doSort(short[] a, int left, int right) {
1.1023 - // Use Quicksort on small arrays
1.1024 - if (right - left < QUICKSORT_THRESHOLD) {
1.1025 - sort(a, left, right, true);
1.1026 - return;
1.1027 - }
1.1028 -
1.1029 - /*
1.1030 - * Index run[i] is the start of i-th run
1.1031 - * (ascending or descending sequence).
1.1032 - */
1.1033 - int[] run = new int[MAX_RUN_COUNT + 1];
1.1034 - int count = 0; run[0] = left;
1.1035 -
1.1036 - // Check if the array is nearly sorted
1.1037 - for (int k = left; k < right; run[count] = k) {
1.1038 - if (a[k] < a[k + 1]) { // ascending
1.1039 - while (++k <= right && a[k - 1] <= a[k]);
1.1040 - } else if (a[k] > a[k + 1]) { // descending
1.1041 - while (++k <= right && a[k - 1] >= a[k]);
1.1042 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.1043 - short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.1044 - }
1.1045 - } else { // equal
1.1046 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.1047 - if (--m == 0) {
1.1048 - sort(a, left, right, true);
1.1049 - return;
1.1050 - }
1.1051 - }
1.1052 - }
1.1053 -
1.1054 - /*
1.1055 - * The array is not highly structured,
1.1056 - * use Quicksort instead of merge sort.
1.1057 - */
1.1058 - if (++count == MAX_RUN_COUNT) {
1.1059 - sort(a, left, right, true);
1.1060 - return;
1.1061 - }
1.1062 - }
1.1063 -
1.1064 - // Check special cases
1.1065 - if (run[count] == right++) { // The last run contains one element
1.1066 - run[++count] = right;
1.1067 - } else if (count == 1) { // The array is already sorted
1.1068 - return;
1.1069 - }
1.1070 -
1.1071 - /*
1.1072 - * Create temporary array, which is used for merging.
1.1073 - * Implementation note: variable "right" is increased by 1.
1.1074 - */
1.1075 - short[] b; byte odd = 0;
1.1076 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.1077 -
1.1078 - if (odd == 0) {
1.1079 - b = a; a = new short[b.length];
1.1080 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.1081 - } else {
1.1082 - b = new short[a.length];
1.1083 - }
1.1084 -
1.1085 - // Merging
1.1086 - for (int last; count > 1; count = last) {
1.1087 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.1088 - int hi = run[k], mi = run[k - 1];
1.1089 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.1090 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.1091 - b[i] = a[p++];
1.1092 - } else {
1.1093 - b[i] = a[q++];
1.1094 - }
1.1095 - }
1.1096 - run[++last] = hi;
1.1097 - }
1.1098 - if ((count & 1) != 0) {
1.1099 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.1100 - b[i] = a[i]
1.1101 - );
1.1102 - run[++last] = right;
1.1103 - }
1.1104 - short[] t = a; a = b; b = t;
1.1105 - }
1.1106 - }
1.1107 -
1.1108 - /**
1.1109 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.1110 - *
1.1111 - * @param a the array to be sorted
1.1112 - * @param left the index of the first element, inclusive, to be sorted
1.1113 - * @param right the index of the last element, inclusive, to be sorted
1.1114 - * @param leftmost indicates if this part is the leftmost in the range
1.1115 - */
1.1116 - private static void sort(short[] a, int left, int right, boolean leftmost) {
1.1117 - int length = right - left + 1;
1.1118 -
1.1119 - // Use insertion sort on tiny arrays
1.1120 - if (length < INSERTION_SORT_THRESHOLD) {
1.1121 - if (leftmost) {
1.1122 - /*
1.1123 - * Traditional (without sentinel) insertion sort,
1.1124 - * optimized for server VM, is used in case of
1.1125 - * the leftmost part.
1.1126 - */
1.1127 - for (int i = left, j = i; i < right; j = ++i) {
1.1128 - short ai = a[i + 1];
1.1129 - while (ai < a[j]) {
1.1130 - a[j + 1] = a[j];
1.1131 - if (j-- == left) {
1.1132 - break;
1.1133 - }
1.1134 - }
1.1135 - a[j + 1] = ai;
1.1136 - }
1.1137 - } else {
1.1138 - /*
1.1139 - * Skip the longest ascending sequence.
1.1140 - */
1.1141 - do {
1.1142 - if (left >= right) {
1.1143 - return;
1.1144 - }
1.1145 - } while (a[++left] >= a[left - 1]);
1.1146 -
1.1147 - /*
1.1148 - * Every element from adjoining part plays the role
1.1149 - * of sentinel, therefore this allows us to avoid the
1.1150 - * left range check on each iteration. Moreover, we use
1.1151 - * the more optimized algorithm, so called pair insertion
1.1152 - * sort, which is faster (in the context of Quicksort)
1.1153 - * than traditional implementation of insertion sort.
1.1154 - */
1.1155 - for (int k = left; ++left <= right; k = ++left) {
1.1156 - short a1 = a[k], a2 = a[left];
1.1157 -
1.1158 - if (a1 < a2) {
1.1159 - a2 = a1; a1 = a[left];
1.1160 - }
1.1161 - while (a1 < a[--k]) {
1.1162 - a[k + 2] = a[k];
1.1163 - }
1.1164 - a[++k + 1] = a1;
1.1165 -
1.1166 - while (a2 < a[--k]) {
1.1167 - a[k + 1] = a[k];
1.1168 - }
1.1169 - a[k + 1] = a2;
1.1170 - }
1.1171 - short last = a[right];
1.1172 -
1.1173 - while (last < a[--right]) {
1.1174 - a[right + 1] = a[right];
1.1175 - }
1.1176 - a[right + 1] = last;
1.1177 - }
1.1178 - return;
1.1179 - }
1.1180 -
1.1181 - // Inexpensive approximation of length / 7
1.1182 - int seventh = (length >> 3) + (length >> 6) + 1;
1.1183 -
1.1184 - /*
1.1185 - * Sort five evenly spaced elements around (and including) the
1.1186 - * center element in the range. These elements will be used for
1.1187 - * pivot selection as described below. The choice for spacing
1.1188 - * these elements was empirically determined to work well on
1.1189 - * a wide variety of inputs.
1.1190 - */
1.1191 - int e3 = (left + right) >>> 1; // The midpoint
1.1192 - int e2 = e3 - seventh;
1.1193 - int e1 = e2 - seventh;
1.1194 - int e4 = e3 + seventh;
1.1195 - int e5 = e4 + seventh;
1.1196 -
1.1197 - // Sort these elements using insertion sort
1.1198 - if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.1199 -
1.1200 - if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.1201 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1202 - }
1.1203 - if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.1204 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.1205 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1206 - }
1.1207 - }
1.1208 - if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.1209 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.1210 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.1211 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1212 - }
1.1213 - }
1.1214 - }
1.1215 -
1.1216 - // Pointers
1.1217 - int less = left; // The index of the first element of center part
1.1218 - int great = right; // The index before the first element of right part
1.1219 -
1.1220 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.1221 - /*
1.1222 - * Use the second and fourth of the five sorted elements as pivots.
1.1223 - * These values are inexpensive approximations of the first and
1.1224 - * second terciles of the array. Note that pivot1 <= pivot2.
1.1225 - */
1.1226 - short pivot1 = a[e2];
1.1227 - short pivot2 = a[e4];
1.1228 -
1.1229 - /*
1.1230 - * The first and the last elements to be sorted are moved to the
1.1231 - * locations formerly occupied by the pivots. When partitioning
1.1232 - * is complete, the pivots are swapped back into their final
1.1233 - * positions, and excluded from subsequent sorting.
1.1234 - */
1.1235 - a[e2] = a[left];
1.1236 - a[e4] = a[right];
1.1237 -
1.1238 - /*
1.1239 - * Skip elements, which are less or greater than pivot values.
1.1240 - */
1.1241 - while (a[++less] < pivot1);
1.1242 - while (a[--great] > pivot2);
1.1243 -
1.1244 - /*
1.1245 - * Partitioning:
1.1246 - *
1.1247 - * left part center part right part
1.1248 - * +--------------------------------------------------------------+
1.1249 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.1250 - * +--------------------------------------------------------------+
1.1251 - * ^ ^ ^
1.1252 - * | | |
1.1253 - * less k great
1.1254 - *
1.1255 - * Invariants:
1.1256 - *
1.1257 - * all in (left, less) < pivot1
1.1258 - * pivot1 <= all in [less, k) <= pivot2
1.1259 - * all in (great, right) > pivot2
1.1260 - *
1.1261 - * Pointer k is the first index of ?-part.
1.1262 - */
1.1263 - outer:
1.1264 - for (int k = less - 1; ++k <= great; ) {
1.1265 - short ak = a[k];
1.1266 - if (ak < pivot1) { // Move a[k] to left part
1.1267 - a[k] = a[less];
1.1268 - /*
1.1269 - * Here and below we use "a[i] = b; i++;" instead
1.1270 - * of "a[i++] = b;" due to performance issue.
1.1271 - */
1.1272 - a[less] = ak;
1.1273 - ++less;
1.1274 - } else if (ak > pivot2) { // Move a[k] to right part
1.1275 - while (a[great] > pivot2) {
1.1276 - if (great-- == k) {
1.1277 - break outer;
1.1278 - }
1.1279 - }
1.1280 - if (a[great] < pivot1) { // a[great] <= pivot2
1.1281 - a[k] = a[less];
1.1282 - a[less] = a[great];
1.1283 - ++less;
1.1284 - } else { // pivot1 <= a[great] <= pivot2
1.1285 - a[k] = a[great];
1.1286 - }
1.1287 - /*
1.1288 - * Here and below we use "a[i] = b; i--;" instead
1.1289 - * of "a[i--] = b;" due to performance issue.
1.1290 - */
1.1291 - a[great] = ak;
1.1292 - --great;
1.1293 - }
1.1294 - }
1.1295 -
1.1296 - // Swap pivots into their final positions
1.1297 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.1298 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.1299 -
1.1300 - // Sort left and right parts recursively, excluding known pivots
1.1301 - sort(a, left, less - 2, leftmost);
1.1302 - sort(a, great + 2, right, false);
1.1303 -
1.1304 - /*
1.1305 - * If center part is too large (comprises > 4/7 of the array),
1.1306 - * swap internal pivot values to ends.
1.1307 - */
1.1308 - if (less < e1 && e5 < great) {
1.1309 - /*
1.1310 - * Skip elements, which are equal to pivot values.
1.1311 - */
1.1312 - while (a[less] == pivot1) {
1.1313 - ++less;
1.1314 - }
1.1315 -
1.1316 - while (a[great] == pivot2) {
1.1317 - --great;
1.1318 - }
1.1319 -
1.1320 - /*
1.1321 - * Partitioning:
1.1322 - *
1.1323 - * left part center part right part
1.1324 - * +----------------------------------------------------------+
1.1325 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.1326 - * +----------------------------------------------------------+
1.1327 - * ^ ^ ^
1.1328 - * | | |
1.1329 - * less k great
1.1330 - *
1.1331 - * Invariants:
1.1332 - *
1.1333 - * all in (*, less) == pivot1
1.1334 - * pivot1 < all in [less, k) < pivot2
1.1335 - * all in (great, *) == pivot2
1.1336 - *
1.1337 - * Pointer k is the first index of ?-part.
1.1338 - */
1.1339 - outer:
1.1340 - for (int k = less - 1; ++k <= great; ) {
1.1341 - short ak = a[k];
1.1342 - if (ak == pivot1) { // Move a[k] to left part
1.1343 - a[k] = a[less];
1.1344 - a[less] = ak;
1.1345 - ++less;
1.1346 - } else if (ak == pivot2) { // Move a[k] to right part
1.1347 - while (a[great] == pivot2) {
1.1348 - if (great-- == k) {
1.1349 - break outer;
1.1350 - }
1.1351 - }
1.1352 - if (a[great] == pivot1) { // a[great] < pivot2
1.1353 - a[k] = a[less];
1.1354 - /*
1.1355 - * Even though a[great] equals to pivot1, the
1.1356 - * assignment a[less] = pivot1 may be incorrect,
1.1357 - * if a[great] and pivot1 are floating-point zeros
1.1358 - * of different signs. Therefore in float and
1.1359 - * double sorting methods we have to use more
1.1360 - * accurate assignment a[less] = a[great].
1.1361 - */
1.1362 - a[less] = pivot1;
1.1363 - ++less;
1.1364 - } else { // pivot1 < a[great] < pivot2
1.1365 - a[k] = a[great];
1.1366 - }
1.1367 - a[great] = ak;
1.1368 - --great;
1.1369 - }
1.1370 - }
1.1371 - }
1.1372 -
1.1373 - // Sort center part recursively
1.1374 - sort(a, less, great, false);
1.1375 -
1.1376 - } else { // Partitioning with one pivot
1.1377 - /*
1.1378 - * Use the third of the five sorted elements as pivot.
1.1379 - * This value is inexpensive approximation of the median.
1.1380 - */
1.1381 - short pivot = a[e3];
1.1382 -
1.1383 - /*
1.1384 - * Partitioning degenerates to the traditional 3-way
1.1385 - * (or "Dutch National Flag") schema:
1.1386 - *
1.1387 - * left part center part right part
1.1388 - * +-------------------------------------------------+
1.1389 - * | < pivot | == pivot | ? | > pivot |
1.1390 - * +-------------------------------------------------+
1.1391 - * ^ ^ ^
1.1392 - * | | |
1.1393 - * less k great
1.1394 - *
1.1395 - * Invariants:
1.1396 - *
1.1397 - * all in (left, less) < pivot
1.1398 - * all in [less, k) == pivot
1.1399 - * all in (great, right) > pivot
1.1400 - *
1.1401 - * Pointer k is the first index of ?-part.
1.1402 - */
1.1403 - for (int k = less; k <= great; ++k) {
1.1404 - if (a[k] == pivot) {
1.1405 - continue;
1.1406 - }
1.1407 - short ak = a[k];
1.1408 - if (ak < pivot) { // Move a[k] to left part
1.1409 - a[k] = a[less];
1.1410 - a[less] = ak;
1.1411 - ++less;
1.1412 - } else { // a[k] > pivot - Move a[k] to right part
1.1413 - while (a[great] > pivot) {
1.1414 - --great;
1.1415 - }
1.1416 - if (a[great] < pivot) { // a[great] <= pivot
1.1417 - a[k] = a[less];
1.1418 - a[less] = a[great];
1.1419 - ++less;
1.1420 - } else { // a[great] == pivot
1.1421 - /*
1.1422 - * Even though a[great] equals to pivot, the
1.1423 - * assignment a[k] = pivot may be incorrect,
1.1424 - * if a[great] and pivot are floating-point
1.1425 - * zeros of different signs. Therefore in float
1.1426 - * and double sorting methods we have to use
1.1427 - * more accurate assignment a[k] = a[great].
1.1428 - */
1.1429 - a[k] = pivot;
1.1430 - }
1.1431 - a[great] = ak;
1.1432 - --great;
1.1433 - }
1.1434 - }
1.1435 -
1.1436 - /*
1.1437 - * Sort left and right parts recursively.
1.1438 - * All elements from center part are equal
1.1439 - * and, therefore, already sorted.
1.1440 - */
1.1441 - sort(a, left, less - 1, leftmost);
1.1442 - sort(a, great + 1, right, false);
1.1443 - }
1.1444 - }
1.1445 -
1.1446 - /**
1.1447 - * Sorts the specified array.
1.1448 - *
1.1449 - * @param a the array to be sorted
1.1450 - */
1.1451 - public static void sort(char[] a) {
1.1452 - sort(a, 0, a.length - 1);
1.1453 - }
1.1454 -
1.1455 - /**
1.1456 - * Sorts the specified range of the array.
1.1457 - *
1.1458 - * @param a the array to be sorted
1.1459 - * @param left the index of the first element, inclusive, to be sorted
1.1460 - * @param right the index of the last element, inclusive, to be sorted
1.1461 - */
1.1462 - public static void sort(char[] a, int left, int right) {
1.1463 - // Use counting sort on large arrays
1.1464 - if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
1.1465 - int[] count = new int[NUM_CHAR_VALUES];
1.1466 -
1.1467 - for (int i = left - 1; ++i <= right;
1.1468 - count[a[i]]++
1.1469 - );
1.1470 - for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
1.1471 - while (count[--i] == 0);
1.1472 - char value = (char) i;
1.1473 - int s = count[i];
1.1474 -
1.1475 - do {
1.1476 - a[--k] = value;
1.1477 - } while (--s > 0);
1.1478 - }
1.1479 - } else { // Use Dual-Pivot Quicksort on small arrays
1.1480 - doSort(a, left, right);
1.1481 - }
1.1482 - }
1.1483 -
1.1484 - /** The number of distinct char values. */
1.1485 - private static final int NUM_CHAR_VALUES = 1 << 16;
1.1486 -
1.1487 - /**
1.1488 - * Sorts the specified range of the array.
1.1489 - *
1.1490 - * @param a the array to be sorted
1.1491 - * @param left the index of the first element, inclusive, to be sorted
1.1492 - * @param right the index of the last element, inclusive, to be sorted
1.1493 - */
1.1494 - private static void doSort(char[] a, int left, int right) {
1.1495 - // Use Quicksort on small arrays
1.1496 - if (right - left < QUICKSORT_THRESHOLD) {
1.1497 - sort(a, left, right, true);
1.1498 - return;
1.1499 - }
1.1500 -
1.1501 - /*
1.1502 - * Index run[i] is the start of i-th run
1.1503 - * (ascending or descending sequence).
1.1504 - */
1.1505 - int[] run = new int[MAX_RUN_COUNT + 1];
1.1506 - int count = 0; run[0] = left;
1.1507 -
1.1508 - // Check if the array is nearly sorted
1.1509 - for (int k = left; k < right; run[count] = k) {
1.1510 - if (a[k] < a[k + 1]) { // ascending
1.1511 - while (++k <= right && a[k - 1] <= a[k]);
1.1512 - } else if (a[k] > a[k + 1]) { // descending
1.1513 - while (++k <= right && a[k - 1] >= a[k]);
1.1514 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.1515 - char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.1516 - }
1.1517 - } else { // equal
1.1518 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.1519 - if (--m == 0) {
1.1520 - sort(a, left, right, true);
1.1521 - return;
1.1522 - }
1.1523 - }
1.1524 - }
1.1525 -
1.1526 - /*
1.1527 - * The array is not highly structured,
1.1528 - * use Quicksort instead of merge sort.
1.1529 - */
1.1530 - if (++count == MAX_RUN_COUNT) {
1.1531 - sort(a, left, right, true);
1.1532 - return;
1.1533 - }
1.1534 - }
1.1535 -
1.1536 - // Check special cases
1.1537 - if (run[count] == right++) { // The last run contains one element
1.1538 - run[++count] = right;
1.1539 - } else if (count == 1) { // The array is already sorted
1.1540 - return;
1.1541 - }
1.1542 -
1.1543 - /*
1.1544 - * Create temporary array, which is used for merging.
1.1545 - * Implementation note: variable "right" is increased by 1.
1.1546 - */
1.1547 - char[] b; byte odd = 0;
1.1548 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.1549 -
1.1550 - if (odd == 0) {
1.1551 - b = a; a = new char[b.length];
1.1552 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.1553 - } else {
1.1554 - b = new char[a.length];
1.1555 - }
1.1556 -
1.1557 - // Merging
1.1558 - for (int last; count > 1; count = last) {
1.1559 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.1560 - int hi = run[k], mi = run[k - 1];
1.1561 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.1562 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.1563 - b[i] = a[p++];
1.1564 - } else {
1.1565 - b[i] = a[q++];
1.1566 - }
1.1567 - }
1.1568 - run[++last] = hi;
1.1569 - }
1.1570 - if ((count & 1) != 0) {
1.1571 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.1572 - b[i] = a[i]
1.1573 - );
1.1574 - run[++last] = right;
1.1575 - }
1.1576 - char[] t = a; a = b; b = t;
1.1577 - }
1.1578 - }
1.1579 -
1.1580 - /**
1.1581 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.1582 - *
1.1583 - * @param a the array to be sorted
1.1584 - * @param left the index of the first element, inclusive, to be sorted
1.1585 - * @param right the index of the last element, inclusive, to be sorted
1.1586 - * @param leftmost indicates if this part is the leftmost in the range
1.1587 - */
1.1588 - private static void sort(char[] a, int left, int right, boolean leftmost) {
1.1589 - int length = right - left + 1;
1.1590 -
1.1591 - // Use insertion sort on tiny arrays
1.1592 - if (length < INSERTION_SORT_THRESHOLD) {
1.1593 - if (leftmost) {
1.1594 - /*
1.1595 - * Traditional (without sentinel) insertion sort,
1.1596 - * optimized for server VM, is used in case of
1.1597 - * the leftmost part.
1.1598 - */
1.1599 - for (int i = left, j = i; i < right; j = ++i) {
1.1600 - char ai = a[i + 1];
1.1601 - while (ai < a[j]) {
1.1602 - a[j + 1] = a[j];
1.1603 - if (j-- == left) {
1.1604 - break;
1.1605 - }
1.1606 - }
1.1607 - a[j + 1] = ai;
1.1608 - }
1.1609 - } else {
1.1610 - /*
1.1611 - * Skip the longest ascending sequence.
1.1612 - */
1.1613 - do {
1.1614 - if (left >= right) {
1.1615 - return;
1.1616 - }
1.1617 - } while (a[++left] >= a[left - 1]);
1.1618 -
1.1619 - /*
1.1620 - * Every element from adjoining part plays the role
1.1621 - * of sentinel, therefore this allows us to avoid the
1.1622 - * left range check on each iteration. Moreover, we use
1.1623 - * the more optimized algorithm, so called pair insertion
1.1624 - * sort, which is faster (in the context of Quicksort)
1.1625 - * than traditional implementation of insertion sort.
1.1626 - */
1.1627 - for (int k = left; ++left <= right; k = ++left) {
1.1628 - char a1 = a[k], a2 = a[left];
1.1629 -
1.1630 - if (a1 < a2) {
1.1631 - a2 = a1; a1 = a[left];
1.1632 - }
1.1633 - while (a1 < a[--k]) {
1.1634 - a[k + 2] = a[k];
1.1635 - }
1.1636 - a[++k + 1] = a1;
1.1637 -
1.1638 - while (a2 < a[--k]) {
1.1639 - a[k + 1] = a[k];
1.1640 - }
1.1641 - a[k + 1] = a2;
1.1642 - }
1.1643 - char last = a[right];
1.1644 -
1.1645 - while (last < a[--right]) {
1.1646 - a[right + 1] = a[right];
1.1647 - }
1.1648 - a[right + 1] = last;
1.1649 - }
1.1650 - return;
1.1651 - }
1.1652 -
1.1653 - // Inexpensive approximation of length / 7
1.1654 - int seventh = (length >> 3) + (length >> 6) + 1;
1.1655 -
1.1656 - /*
1.1657 - * Sort five evenly spaced elements around (and including) the
1.1658 - * center element in the range. These elements will be used for
1.1659 - * pivot selection as described below. The choice for spacing
1.1660 - * these elements was empirically determined to work well on
1.1661 - * a wide variety of inputs.
1.1662 - */
1.1663 - int e3 = (left + right) >>> 1; // The midpoint
1.1664 - int e2 = e3 - seventh;
1.1665 - int e1 = e2 - seventh;
1.1666 - int e4 = e3 + seventh;
1.1667 - int e5 = e4 + seventh;
1.1668 -
1.1669 - // Sort these elements using insertion sort
1.1670 - if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.1671 -
1.1672 - if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.1673 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1674 - }
1.1675 - if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.1676 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.1677 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1678 - }
1.1679 - }
1.1680 - if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.1681 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.1682 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.1683 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.1684 - }
1.1685 - }
1.1686 - }
1.1687 -
1.1688 - // Pointers
1.1689 - int less = left; // The index of the first element of center part
1.1690 - int great = right; // The index before the first element of right part
1.1691 -
1.1692 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.1693 - /*
1.1694 - * Use the second and fourth of the five sorted elements as pivots.
1.1695 - * These values are inexpensive approximations of the first and
1.1696 - * second terciles of the array. Note that pivot1 <= pivot2.
1.1697 - */
1.1698 - char pivot1 = a[e2];
1.1699 - char pivot2 = a[e4];
1.1700 -
1.1701 - /*
1.1702 - * The first and the last elements to be sorted are moved to the
1.1703 - * locations formerly occupied by the pivots. When partitioning
1.1704 - * is complete, the pivots are swapped back into their final
1.1705 - * positions, and excluded from subsequent sorting.
1.1706 - */
1.1707 - a[e2] = a[left];
1.1708 - a[e4] = a[right];
1.1709 -
1.1710 - /*
1.1711 - * Skip elements, which are less or greater than pivot values.
1.1712 - */
1.1713 - while (a[++less] < pivot1);
1.1714 - while (a[--great] > pivot2);
1.1715 -
1.1716 - /*
1.1717 - * Partitioning:
1.1718 - *
1.1719 - * left part center part right part
1.1720 - * +--------------------------------------------------------------+
1.1721 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.1722 - * +--------------------------------------------------------------+
1.1723 - * ^ ^ ^
1.1724 - * | | |
1.1725 - * less k great
1.1726 - *
1.1727 - * Invariants:
1.1728 - *
1.1729 - * all in (left, less) < pivot1
1.1730 - * pivot1 <= all in [less, k) <= pivot2
1.1731 - * all in (great, right) > pivot2
1.1732 - *
1.1733 - * Pointer k is the first index of ?-part.
1.1734 - */
1.1735 - outer:
1.1736 - for (int k = less - 1; ++k <= great; ) {
1.1737 - char ak = a[k];
1.1738 - if (ak < pivot1) { // Move a[k] to left part
1.1739 - a[k] = a[less];
1.1740 - /*
1.1741 - * Here and below we use "a[i] = b; i++;" instead
1.1742 - * of "a[i++] = b;" due to performance issue.
1.1743 - */
1.1744 - a[less] = ak;
1.1745 - ++less;
1.1746 - } else if (ak > pivot2) { // Move a[k] to right part
1.1747 - while (a[great] > pivot2) {
1.1748 - if (great-- == k) {
1.1749 - break outer;
1.1750 - }
1.1751 - }
1.1752 - if (a[great] < pivot1) { // a[great] <= pivot2
1.1753 - a[k] = a[less];
1.1754 - a[less] = a[great];
1.1755 - ++less;
1.1756 - } else { // pivot1 <= a[great] <= pivot2
1.1757 - a[k] = a[great];
1.1758 - }
1.1759 - /*
1.1760 - * Here and below we use "a[i] = b; i--;" instead
1.1761 - * of "a[i--] = b;" due to performance issue.
1.1762 - */
1.1763 - a[great] = ak;
1.1764 - --great;
1.1765 - }
1.1766 - }
1.1767 -
1.1768 - // Swap pivots into their final positions
1.1769 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.1770 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.1771 -
1.1772 - // Sort left and right parts recursively, excluding known pivots
1.1773 - sort(a, left, less - 2, leftmost);
1.1774 - sort(a, great + 2, right, false);
1.1775 -
1.1776 - /*
1.1777 - * If center part is too large (comprises > 4/7 of the array),
1.1778 - * swap internal pivot values to ends.
1.1779 - */
1.1780 - if (less < e1 && e5 < great) {
1.1781 - /*
1.1782 - * Skip elements, which are equal to pivot values.
1.1783 - */
1.1784 - while (a[less] == pivot1) {
1.1785 - ++less;
1.1786 - }
1.1787 -
1.1788 - while (a[great] == pivot2) {
1.1789 - --great;
1.1790 - }
1.1791 -
1.1792 - /*
1.1793 - * Partitioning:
1.1794 - *
1.1795 - * left part center part right part
1.1796 - * +----------------------------------------------------------+
1.1797 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.1798 - * +----------------------------------------------------------+
1.1799 - * ^ ^ ^
1.1800 - * | | |
1.1801 - * less k great
1.1802 - *
1.1803 - * Invariants:
1.1804 - *
1.1805 - * all in (*, less) == pivot1
1.1806 - * pivot1 < all in [less, k) < pivot2
1.1807 - * all in (great, *) == pivot2
1.1808 - *
1.1809 - * Pointer k is the first index of ?-part.
1.1810 - */
1.1811 - outer:
1.1812 - for (int k = less - 1; ++k <= great; ) {
1.1813 - char ak = a[k];
1.1814 - if (ak == pivot1) { // Move a[k] to left part
1.1815 - a[k] = a[less];
1.1816 - a[less] = ak;
1.1817 - ++less;
1.1818 - } else if (ak == pivot2) { // Move a[k] to right part
1.1819 - while (a[great] == pivot2) {
1.1820 - if (great-- == k) {
1.1821 - break outer;
1.1822 - }
1.1823 - }
1.1824 - if (a[great] == pivot1) { // a[great] < pivot2
1.1825 - a[k] = a[less];
1.1826 - /*
1.1827 - * Even though a[great] equals to pivot1, the
1.1828 - * assignment a[less] = pivot1 may be incorrect,
1.1829 - * if a[great] and pivot1 are floating-point zeros
1.1830 - * of different signs. Therefore in float and
1.1831 - * double sorting methods we have to use more
1.1832 - * accurate assignment a[less] = a[great].
1.1833 - */
1.1834 - a[less] = pivot1;
1.1835 - ++less;
1.1836 - } else { // pivot1 < a[great] < pivot2
1.1837 - a[k] = a[great];
1.1838 - }
1.1839 - a[great] = ak;
1.1840 - --great;
1.1841 - }
1.1842 - }
1.1843 - }
1.1844 -
1.1845 - // Sort center part recursively
1.1846 - sort(a, less, great, false);
1.1847 -
1.1848 - } else { // Partitioning with one pivot
1.1849 - /*
1.1850 - * Use the third of the five sorted elements as pivot.
1.1851 - * This value is inexpensive approximation of the median.
1.1852 - */
1.1853 - char pivot = a[e3];
1.1854 -
1.1855 - /*
1.1856 - * Partitioning degenerates to the traditional 3-way
1.1857 - * (or "Dutch National Flag") schema:
1.1858 - *
1.1859 - * left part center part right part
1.1860 - * +-------------------------------------------------+
1.1861 - * | < pivot | == pivot | ? | > pivot |
1.1862 - * +-------------------------------------------------+
1.1863 - * ^ ^ ^
1.1864 - * | | |
1.1865 - * less k great
1.1866 - *
1.1867 - * Invariants:
1.1868 - *
1.1869 - * all in (left, less) < pivot
1.1870 - * all in [less, k) == pivot
1.1871 - * all in (great, right) > pivot
1.1872 - *
1.1873 - * Pointer k is the first index of ?-part.
1.1874 - */
1.1875 - for (int k = less; k <= great; ++k) {
1.1876 - if (a[k] == pivot) {
1.1877 - continue;
1.1878 - }
1.1879 - char ak = a[k];
1.1880 - if (ak < pivot) { // Move a[k] to left part
1.1881 - a[k] = a[less];
1.1882 - a[less] = ak;
1.1883 - ++less;
1.1884 - } else { // a[k] > pivot - Move a[k] to right part
1.1885 - while (a[great] > pivot) {
1.1886 - --great;
1.1887 - }
1.1888 - if (a[great] < pivot) { // a[great] <= pivot
1.1889 - a[k] = a[less];
1.1890 - a[less] = a[great];
1.1891 - ++less;
1.1892 - } else { // a[great] == pivot
1.1893 - /*
1.1894 - * Even though a[great] equals to pivot, the
1.1895 - * assignment a[k] = pivot may be incorrect,
1.1896 - * if a[great] and pivot are floating-point
1.1897 - * zeros of different signs. Therefore in float
1.1898 - * and double sorting methods we have to use
1.1899 - * more accurate assignment a[k] = a[great].
1.1900 - */
1.1901 - a[k] = pivot;
1.1902 - }
1.1903 - a[great] = ak;
1.1904 - --great;
1.1905 - }
1.1906 - }
1.1907 -
1.1908 - /*
1.1909 - * Sort left and right parts recursively.
1.1910 - * All elements from center part are equal
1.1911 - * and, therefore, already sorted.
1.1912 - */
1.1913 - sort(a, left, less - 1, leftmost);
1.1914 - sort(a, great + 1, right, false);
1.1915 - }
1.1916 - }
1.1917 -
1.1918 - /** The number of distinct byte values. */
1.1919 - private static final int NUM_BYTE_VALUES = 1 << 8;
1.1920 -
1.1921 - /**
1.1922 - * Sorts the specified array.
1.1923 - *
1.1924 - * @param a the array to be sorted
1.1925 - */
1.1926 - public static void sort(byte[] a) {
1.1927 - sort(a, 0, a.length - 1);
1.1928 - }
1.1929 -
1.1930 - /**
1.1931 - * Sorts the specified range of the array.
1.1932 - *
1.1933 - * @param a the array to be sorted
1.1934 - * @param left the index of the first element, inclusive, to be sorted
1.1935 - * @param right the index of the last element, inclusive, to be sorted
1.1936 - */
1.1937 - public static void sort(byte[] a, int left, int right) {
1.1938 - // Use counting sort on large arrays
1.1939 - if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
1.1940 - int[] count = new int[NUM_BYTE_VALUES];
1.1941 -
1.1942 - for (int i = left - 1; ++i <= right;
1.1943 - count[a[i] - Byte.MIN_VALUE]++
1.1944 - );
1.1945 - for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
1.1946 - while (count[--i] == 0);
1.1947 - byte value = (byte) (i + Byte.MIN_VALUE);
1.1948 - int s = count[i];
1.1949 -
1.1950 - do {
1.1951 - a[--k] = value;
1.1952 - } while (--s > 0);
1.1953 - }
1.1954 - } else { // Use insertion sort on small arrays
1.1955 - for (int i = left, j = i; i < right; j = ++i) {
1.1956 - byte ai = a[i + 1];
1.1957 - while (ai < a[j]) {
1.1958 - a[j + 1] = a[j];
1.1959 - if (j-- == left) {
1.1960 - break;
1.1961 - }
1.1962 - }
1.1963 - a[j + 1] = ai;
1.1964 - }
1.1965 - }
1.1966 - }
1.1967 -
1.1968 - /**
1.1969 - * Sorts the specified array.
1.1970 - *
1.1971 - * @param a the array to be sorted
1.1972 - */
1.1973 - public static void sort(float[] a) {
1.1974 - sort(a, 0, a.length - 1);
1.1975 - }
1.1976 -
1.1977 - /**
1.1978 - * Sorts the specified range of the array.
1.1979 - *
1.1980 - * @param a the array to be sorted
1.1981 - * @param left the index of the first element, inclusive, to be sorted
1.1982 - * @param right the index of the last element, inclusive, to be sorted
1.1983 - */
1.1984 - public static void sort(float[] a, int left, int right) {
1.1985 - /*
1.1986 - * Phase 1: Move NaNs to the end of the array.
1.1987 - */
1.1988 - while (left <= right && Float.isNaN(a[right])) {
1.1989 - --right;
1.1990 - }
1.1991 - for (int k = right; --k >= left; ) {
1.1992 - float ak = a[k];
1.1993 - if (ak != ak) { // a[k] is NaN
1.1994 - a[k] = a[right];
1.1995 - a[right] = ak;
1.1996 - --right;
1.1997 - }
1.1998 - }
1.1999 -
1.2000 - /*
1.2001 - * Phase 2: Sort everything except NaNs (which are already in place).
1.2002 - */
1.2003 - doSort(a, left, right);
1.2004 -
1.2005 - /*
1.2006 - * Phase 3: Place negative zeros before positive zeros.
1.2007 - */
1.2008 - int hi = right;
1.2009 -
1.2010 - /*
1.2011 - * Find the first zero, or first positive, or last negative element.
1.2012 - */
1.2013 - while (left < hi) {
1.2014 - int middle = (left + hi) >>> 1;
1.2015 - float middleValue = a[middle];
1.2016 -
1.2017 - if (middleValue < 0.0f) {
1.2018 - left = middle + 1;
1.2019 - } else {
1.2020 - hi = middle;
1.2021 - }
1.2022 - }
1.2023 -
1.2024 - /*
1.2025 - * Skip the last negative value (if any) or all leading negative zeros.
1.2026 - */
1.2027 - while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
1.2028 - ++left;
1.2029 - }
1.2030 -
1.2031 - /*
1.2032 - * Move negative zeros to the beginning of the sub-range.
1.2033 - *
1.2034 - * Partitioning:
1.2035 - *
1.2036 - * +----------------------------------------------------+
1.2037 - * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
1.2038 - * +----------------------------------------------------+
1.2039 - * ^ ^ ^
1.2040 - * | | |
1.2041 - * left p k
1.2042 - *
1.2043 - * Invariants:
1.2044 - *
1.2045 - * all in (*, left) < 0.0
1.2046 - * all in [left, p) == -0.0
1.2047 - * all in [p, k) == 0.0
1.2048 - * all in [k, right] >= 0.0
1.2049 - *
1.2050 - * Pointer k is the first index of ?-part.
1.2051 - */
1.2052 - for (int k = left, p = left - 1; ++k <= right; ) {
1.2053 - float ak = a[k];
1.2054 - if (ak != 0.0f) {
1.2055 - break;
1.2056 - }
1.2057 - if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
1.2058 - a[k] = 0.0f;
1.2059 - a[++p] = -0.0f;
1.2060 - }
1.2061 - }
1.2062 - }
1.2063 -
1.2064 - /**
1.2065 - * Sorts the specified range of the array.
1.2066 - *
1.2067 - * @param a the array to be sorted
1.2068 - * @param left the index of the first element, inclusive, to be sorted
1.2069 - * @param right the index of the last element, inclusive, to be sorted
1.2070 - */
1.2071 - private static void doSort(float[] a, int left, int right) {
1.2072 - // Use Quicksort on small arrays
1.2073 - if (right - left < QUICKSORT_THRESHOLD) {
1.2074 - sort(a, left, right, true);
1.2075 - return;
1.2076 - }
1.2077 -
1.2078 - /*
1.2079 - * Index run[i] is the start of i-th run
1.2080 - * (ascending or descending sequence).
1.2081 - */
1.2082 - int[] run = new int[MAX_RUN_COUNT + 1];
1.2083 - int count = 0; run[0] = left;
1.2084 -
1.2085 - // Check if the array is nearly sorted
1.2086 - for (int k = left; k < right; run[count] = k) {
1.2087 - if (a[k] < a[k + 1]) { // ascending
1.2088 - while (++k <= right && a[k - 1] <= a[k]);
1.2089 - } else if (a[k] > a[k + 1]) { // descending
1.2090 - while (++k <= right && a[k - 1] >= a[k]);
1.2091 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.2092 - float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.2093 - }
1.2094 - } else { // equal
1.2095 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.2096 - if (--m == 0) {
1.2097 - sort(a, left, right, true);
1.2098 - return;
1.2099 - }
1.2100 - }
1.2101 - }
1.2102 -
1.2103 - /*
1.2104 - * The array is not highly structured,
1.2105 - * use Quicksort instead of merge sort.
1.2106 - */
1.2107 - if (++count == MAX_RUN_COUNT) {
1.2108 - sort(a, left, right, true);
1.2109 - return;
1.2110 - }
1.2111 - }
1.2112 -
1.2113 - // Check special cases
1.2114 - if (run[count] == right++) { // The last run contains one element
1.2115 - run[++count] = right;
1.2116 - } else if (count == 1) { // The array is already sorted
1.2117 - return;
1.2118 - }
1.2119 -
1.2120 - /*
1.2121 - * Create temporary array, which is used for merging.
1.2122 - * Implementation note: variable "right" is increased by 1.
1.2123 - */
1.2124 - float[] b; byte odd = 0;
1.2125 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.2126 -
1.2127 - if (odd == 0) {
1.2128 - b = a; a = new float[b.length];
1.2129 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.2130 - } else {
1.2131 - b = new float[a.length];
1.2132 - }
1.2133 -
1.2134 - // Merging
1.2135 - for (int last; count > 1; count = last) {
1.2136 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.2137 - int hi = run[k], mi = run[k - 1];
1.2138 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.2139 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.2140 - b[i] = a[p++];
1.2141 - } else {
1.2142 - b[i] = a[q++];
1.2143 - }
1.2144 - }
1.2145 - run[++last] = hi;
1.2146 - }
1.2147 - if ((count & 1) != 0) {
1.2148 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.2149 - b[i] = a[i]
1.2150 - );
1.2151 - run[++last] = right;
1.2152 - }
1.2153 - float[] t = a; a = b; b = t;
1.2154 - }
1.2155 - }
1.2156 -
1.2157 - /**
1.2158 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.2159 - *
1.2160 - * @param a the array to be sorted
1.2161 - * @param left the index of the first element, inclusive, to be sorted
1.2162 - * @param right the index of the last element, inclusive, to be sorted
1.2163 - * @param leftmost indicates if this part is the leftmost in the range
1.2164 - */
1.2165 - private static void sort(float[] a, int left, int right, boolean leftmost) {
1.2166 - int length = right - left + 1;
1.2167 -
1.2168 - // Use insertion sort on tiny arrays
1.2169 - if (length < INSERTION_SORT_THRESHOLD) {
1.2170 - if (leftmost) {
1.2171 - /*
1.2172 - * Traditional (without sentinel) insertion sort,
1.2173 - * optimized for server VM, is used in case of
1.2174 - * the leftmost part.
1.2175 - */
1.2176 - for (int i = left, j = i; i < right; j = ++i) {
1.2177 - float ai = a[i + 1];
1.2178 - while (ai < a[j]) {
1.2179 - a[j + 1] = a[j];
1.2180 - if (j-- == left) {
1.2181 - break;
1.2182 - }
1.2183 - }
1.2184 - a[j + 1] = ai;
1.2185 - }
1.2186 - } else {
1.2187 - /*
1.2188 - * Skip the longest ascending sequence.
1.2189 - */
1.2190 - do {
1.2191 - if (left >= right) {
1.2192 - return;
1.2193 - }
1.2194 - } while (a[++left] >= a[left - 1]);
1.2195 -
1.2196 - /*
1.2197 - * Every element from adjoining part plays the role
1.2198 - * of sentinel, therefore this allows us to avoid the
1.2199 - * left range check on each iteration. Moreover, we use
1.2200 - * the more optimized algorithm, so called pair insertion
1.2201 - * sort, which is faster (in the context of Quicksort)
1.2202 - * than traditional implementation of insertion sort.
1.2203 - */
1.2204 - for (int k = left; ++left <= right; k = ++left) {
1.2205 - float a1 = a[k], a2 = a[left];
1.2206 -
1.2207 - if (a1 < a2) {
1.2208 - a2 = a1; a1 = a[left];
1.2209 - }
1.2210 - while (a1 < a[--k]) {
1.2211 - a[k + 2] = a[k];
1.2212 - }
1.2213 - a[++k + 1] = a1;
1.2214 -
1.2215 - while (a2 < a[--k]) {
1.2216 - a[k + 1] = a[k];
1.2217 - }
1.2218 - a[k + 1] = a2;
1.2219 - }
1.2220 - float last = a[right];
1.2221 -
1.2222 - while (last < a[--right]) {
1.2223 - a[right + 1] = a[right];
1.2224 - }
1.2225 - a[right + 1] = last;
1.2226 - }
1.2227 - return;
1.2228 - }
1.2229 -
1.2230 - // Inexpensive approximation of length / 7
1.2231 - int seventh = (length >> 3) + (length >> 6) + 1;
1.2232 -
1.2233 - /*
1.2234 - * Sort five evenly spaced elements around (and including) the
1.2235 - * center element in the range. These elements will be used for
1.2236 - * pivot selection as described below. The choice for spacing
1.2237 - * these elements was empirically determined to work well on
1.2238 - * a wide variety of inputs.
1.2239 - */
1.2240 - int e3 = (left + right) >>> 1; // The midpoint
1.2241 - int e2 = e3 - seventh;
1.2242 - int e1 = e2 - seventh;
1.2243 - int e4 = e3 + seventh;
1.2244 - int e5 = e4 + seventh;
1.2245 -
1.2246 - // Sort these elements using insertion sort
1.2247 - if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.2248 -
1.2249 - if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.2250 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2251 - }
1.2252 - if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.2253 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.2254 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2255 - }
1.2256 - }
1.2257 - if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.2258 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.2259 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.2260 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2261 - }
1.2262 - }
1.2263 - }
1.2264 -
1.2265 - // Pointers
1.2266 - int less = left; // The index of the first element of center part
1.2267 - int great = right; // The index before the first element of right part
1.2268 -
1.2269 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.2270 - /*
1.2271 - * Use the second and fourth of the five sorted elements as pivots.
1.2272 - * These values are inexpensive approximations of the first and
1.2273 - * second terciles of the array. Note that pivot1 <= pivot2.
1.2274 - */
1.2275 - float pivot1 = a[e2];
1.2276 - float pivot2 = a[e4];
1.2277 -
1.2278 - /*
1.2279 - * The first and the last elements to be sorted are moved to the
1.2280 - * locations formerly occupied by the pivots. When partitioning
1.2281 - * is complete, the pivots are swapped back into their final
1.2282 - * positions, and excluded from subsequent sorting.
1.2283 - */
1.2284 - a[e2] = a[left];
1.2285 - a[e4] = a[right];
1.2286 -
1.2287 - /*
1.2288 - * Skip elements, which are less or greater than pivot values.
1.2289 - */
1.2290 - while (a[++less] < pivot1);
1.2291 - while (a[--great] > pivot2);
1.2292 -
1.2293 - /*
1.2294 - * Partitioning:
1.2295 - *
1.2296 - * left part center part right part
1.2297 - * +--------------------------------------------------------------+
1.2298 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.2299 - * +--------------------------------------------------------------+
1.2300 - * ^ ^ ^
1.2301 - * | | |
1.2302 - * less k great
1.2303 - *
1.2304 - * Invariants:
1.2305 - *
1.2306 - * all in (left, less) < pivot1
1.2307 - * pivot1 <= all in [less, k) <= pivot2
1.2308 - * all in (great, right) > pivot2
1.2309 - *
1.2310 - * Pointer k is the first index of ?-part.
1.2311 - */
1.2312 - outer:
1.2313 - for (int k = less - 1; ++k <= great; ) {
1.2314 - float ak = a[k];
1.2315 - if (ak < pivot1) { // Move a[k] to left part
1.2316 - a[k] = a[less];
1.2317 - /*
1.2318 - * Here and below we use "a[i] = b; i++;" instead
1.2319 - * of "a[i++] = b;" due to performance issue.
1.2320 - */
1.2321 - a[less] = ak;
1.2322 - ++less;
1.2323 - } else if (ak > pivot2) { // Move a[k] to right part
1.2324 - while (a[great] > pivot2) {
1.2325 - if (great-- == k) {
1.2326 - break outer;
1.2327 - }
1.2328 - }
1.2329 - if (a[great] < pivot1) { // a[great] <= pivot2
1.2330 - a[k] = a[less];
1.2331 - a[less] = a[great];
1.2332 - ++less;
1.2333 - } else { // pivot1 <= a[great] <= pivot2
1.2334 - a[k] = a[great];
1.2335 - }
1.2336 - /*
1.2337 - * Here and below we use "a[i] = b; i--;" instead
1.2338 - * of "a[i--] = b;" due to performance issue.
1.2339 - */
1.2340 - a[great] = ak;
1.2341 - --great;
1.2342 - }
1.2343 - }
1.2344 -
1.2345 - // Swap pivots into their final positions
1.2346 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.2347 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.2348 -
1.2349 - // Sort left and right parts recursively, excluding known pivots
1.2350 - sort(a, left, less - 2, leftmost);
1.2351 - sort(a, great + 2, right, false);
1.2352 -
1.2353 - /*
1.2354 - * If center part is too large (comprises > 4/7 of the array),
1.2355 - * swap internal pivot values to ends.
1.2356 - */
1.2357 - if (less < e1 && e5 < great) {
1.2358 - /*
1.2359 - * Skip elements, which are equal to pivot values.
1.2360 - */
1.2361 - while (a[less] == pivot1) {
1.2362 - ++less;
1.2363 - }
1.2364 -
1.2365 - while (a[great] == pivot2) {
1.2366 - --great;
1.2367 - }
1.2368 -
1.2369 - /*
1.2370 - * Partitioning:
1.2371 - *
1.2372 - * left part center part right part
1.2373 - * +----------------------------------------------------------+
1.2374 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.2375 - * +----------------------------------------------------------+
1.2376 - * ^ ^ ^
1.2377 - * | | |
1.2378 - * less k great
1.2379 - *
1.2380 - * Invariants:
1.2381 - *
1.2382 - * all in (*, less) == pivot1
1.2383 - * pivot1 < all in [less, k) < pivot2
1.2384 - * all in (great, *) == pivot2
1.2385 - *
1.2386 - * Pointer k is the first index of ?-part.
1.2387 - */
1.2388 - outer:
1.2389 - for (int k = less - 1; ++k <= great; ) {
1.2390 - float ak = a[k];
1.2391 - if (ak == pivot1) { // Move a[k] to left part
1.2392 - a[k] = a[less];
1.2393 - a[less] = ak;
1.2394 - ++less;
1.2395 - } else if (ak == pivot2) { // Move a[k] to right part
1.2396 - while (a[great] == pivot2) {
1.2397 - if (great-- == k) {
1.2398 - break outer;
1.2399 - }
1.2400 - }
1.2401 - if (a[great] == pivot1) { // a[great] < pivot2
1.2402 - a[k] = a[less];
1.2403 - /*
1.2404 - * Even though a[great] equals to pivot1, the
1.2405 - * assignment a[less] = pivot1 may be incorrect,
1.2406 - * if a[great] and pivot1 are floating-point zeros
1.2407 - * of different signs. Therefore in float and
1.2408 - * double sorting methods we have to use more
1.2409 - * accurate assignment a[less] = a[great].
1.2410 - */
1.2411 - a[less] = a[great];
1.2412 - ++less;
1.2413 - } else { // pivot1 < a[great] < pivot2
1.2414 - a[k] = a[great];
1.2415 - }
1.2416 - a[great] = ak;
1.2417 - --great;
1.2418 - }
1.2419 - }
1.2420 - }
1.2421 -
1.2422 - // Sort center part recursively
1.2423 - sort(a, less, great, false);
1.2424 -
1.2425 - } else { // Partitioning with one pivot
1.2426 - /*
1.2427 - * Use the third of the five sorted elements as pivot.
1.2428 - * This value is inexpensive approximation of the median.
1.2429 - */
1.2430 - float pivot = a[e3];
1.2431 -
1.2432 - /*
1.2433 - * Partitioning degenerates to the traditional 3-way
1.2434 - * (or "Dutch National Flag") schema:
1.2435 - *
1.2436 - * left part center part right part
1.2437 - * +-------------------------------------------------+
1.2438 - * | < pivot | == pivot | ? | > pivot |
1.2439 - * +-------------------------------------------------+
1.2440 - * ^ ^ ^
1.2441 - * | | |
1.2442 - * less k great
1.2443 - *
1.2444 - * Invariants:
1.2445 - *
1.2446 - * all in (left, less) < pivot
1.2447 - * all in [less, k) == pivot
1.2448 - * all in (great, right) > pivot
1.2449 - *
1.2450 - * Pointer k is the first index of ?-part.
1.2451 - */
1.2452 - for (int k = less; k <= great; ++k) {
1.2453 - if (a[k] == pivot) {
1.2454 - continue;
1.2455 - }
1.2456 - float ak = a[k];
1.2457 - if (ak < pivot) { // Move a[k] to left part
1.2458 - a[k] = a[less];
1.2459 - a[less] = ak;
1.2460 - ++less;
1.2461 - } else { // a[k] > pivot - Move a[k] to right part
1.2462 - while (a[great] > pivot) {
1.2463 - --great;
1.2464 - }
1.2465 - if (a[great] < pivot) { // a[great] <= pivot
1.2466 - a[k] = a[less];
1.2467 - a[less] = a[great];
1.2468 - ++less;
1.2469 - } else { // a[great] == pivot
1.2470 - /*
1.2471 - * Even though a[great] equals to pivot, the
1.2472 - * assignment a[k] = pivot may be incorrect,
1.2473 - * if a[great] and pivot are floating-point
1.2474 - * zeros of different signs. Therefore in float
1.2475 - * and double sorting methods we have to use
1.2476 - * more accurate assignment a[k] = a[great].
1.2477 - */
1.2478 - a[k] = a[great];
1.2479 - }
1.2480 - a[great] = ak;
1.2481 - --great;
1.2482 - }
1.2483 - }
1.2484 -
1.2485 - /*
1.2486 - * Sort left and right parts recursively.
1.2487 - * All elements from center part are equal
1.2488 - * and, therefore, already sorted.
1.2489 - */
1.2490 - sort(a, left, less - 1, leftmost);
1.2491 - sort(a, great + 1, right, false);
1.2492 - }
1.2493 - }
1.2494 -
1.2495 - /**
1.2496 - * Sorts the specified array.
1.2497 - *
1.2498 - * @param a the array to be sorted
1.2499 - */
1.2500 - public static void sort(double[] a) {
1.2501 - sort(a, 0, a.length - 1);
1.2502 - }
1.2503 -
1.2504 - /**
1.2505 - * Sorts the specified range of the array.
1.2506 - *
1.2507 - * @param a the array to be sorted
1.2508 - * @param left the index of the first element, inclusive, to be sorted
1.2509 - * @param right the index of the last element, inclusive, to be sorted
1.2510 - */
1.2511 - public static void sort(double[] a, int left, int right) {
1.2512 - /*
1.2513 - * Phase 1: Move NaNs to the end of the array.
1.2514 - */
1.2515 - while (left <= right && Double.isNaN(a[right])) {
1.2516 - --right;
1.2517 - }
1.2518 - for (int k = right; --k >= left; ) {
1.2519 - double ak = a[k];
1.2520 - if (ak != ak) { // a[k] is NaN
1.2521 - a[k] = a[right];
1.2522 - a[right] = ak;
1.2523 - --right;
1.2524 - }
1.2525 - }
1.2526 -
1.2527 - /*
1.2528 - * Phase 2: Sort everything except NaNs (which are already in place).
1.2529 - */
1.2530 - doSort(a, left, right);
1.2531 -
1.2532 - /*
1.2533 - * Phase 3: Place negative zeros before positive zeros.
1.2534 - */
1.2535 - int hi = right;
1.2536 -
1.2537 - /*
1.2538 - * Find the first zero, or first positive, or last negative element.
1.2539 - */
1.2540 - while (left < hi) {
1.2541 - int middle = (left + hi) >>> 1;
1.2542 - double middleValue = a[middle];
1.2543 -
1.2544 - if (middleValue < 0.0d) {
1.2545 - left = middle + 1;
1.2546 - } else {
1.2547 - hi = middle;
1.2548 - }
1.2549 - }
1.2550 -
1.2551 - /*
1.2552 - * Skip the last negative value (if any) or all leading negative zeros.
1.2553 - */
1.2554 - while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
1.2555 - ++left;
1.2556 - }
1.2557 -
1.2558 - /*
1.2559 - * Move negative zeros to the beginning of the sub-range.
1.2560 - *
1.2561 - * Partitioning:
1.2562 - *
1.2563 - * +----------------------------------------------------+
1.2564 - * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
1.2565 - * +----------------------------------------------------+
1.2566 - * ^ ^ ^
1.2567 - * | | |
1.2568 - * left p k
1.2569 - *
1.2570 - * Invariants:
1.2571 - *
1.2572 - * all in (*, left) < 0.0
1.2573 - * all in [left, p) == -0.0
1.2574 - * all in [p, k) == 0.0
1.2575 - * all in [k, right] >= 0.0
1.2576 - *
1.2577 - * Pointer k is the first index of ?-part.
1.2578 - */
1.2579 - for (int k = left, p = left - 1; ++k <= right; ) {
1.2580 - double ak = a[k];
1.2581 - if (ak != 0.0d) {
1.2582 - break;
1.2583 - }
1.2584 - if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
1.2585 - a[k] = 0.0d;
1.2586 - a[++p] = -0.0d;
1.2587 - }
1.2588 - }
1.2589 - }
1.2590 -
1.2591 - /**
1.2592 - * Sorts the specified range of the array.
1.2593 - *
1.2594 - * @param a the array to be sorted
1.2595 - * @param left the index of the first element, inclusive, to be sorted
1.2596 - * @param right the index of the last element, inclusive, to be sorted
1.2597 - */
1.2598 - private static void doSort(double[] a, int left, int right) {
1.2599 - // Use Quicksort on small arrays
1.2600 - if (right - left < QUICKSORT_THRESHOLD) {
1.2601 - sort(a, left, right, true);
1.2602 - return;
1.2603 - }
1.2604 -
1.2605 - /*
1.2606 - * Index run[i] is the start of i-th run
1.2607 - * (ascending or descending sequence).
1.2608 - */
1.2609 - int[] run = new int[MAX_RUN_COUNT + 1];
1.2610 - int count = 0; run[0] = left;
1.2611 -
1.2612 - // Check if the array is nearly sorted
1.2613 - for (int k = left; k < right; run[count] = k) {
1.2614 - if (a[k] < a[k + 1]) { // ascending
1.2615 - while (++k <= right && a[k - 1] <= a[k]);
1.2616 - } else if (a[k] > a[k + 1]) { // descending
1.2617 - while (++k <= right && a[k - 1] >= a[k]);
1.2618 - for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
1.2619 - double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
1.2620 - }
1.2621 - } else { // equal
1.2622 - for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
1.2623 - if (--m == 0) {
1.2624 - sort(a, left, right, true);
1.2625 - return;
1.2626 - }
1.2627 - }
1.2628 - }
1.2629 -
1.2630 - /*
1.2631 - * The array is not highly structured,
1.2632 - * use Quicksort instead of merge sort.
1.2633 - */
1.2634 - if (++count == MAX_RUN_COUNT) {
1.2635 - sort(a, left, right, true);
1.2636 - return;
1.2637 - }
1.2638 - }
1.2639 -
1.2640 - // Check special cases
1.2641 - if (run[count] == right++) { // The last run contains one element
1.2642 - run[++count] = right;
1.2643 - } else if (count == 1) { // The array is already sorted
1.2644 - return;
1.2645 - }
1.2646 -
1.2647 - /*
1.2648 - * Create temporary array, which is used for merging.
1.2649 - * Implementation note: variable "right" is increased by 1.
1.2650 - */
1.2651 - double[] b; byte odd = 0;
1.2652 - for (int n = 1; (n <<= 1) < count; odd ^= 1);
1.2653 -
1.2654 - if (odd == 0) {
1.2655 - b = a; a = new double[b.length];
1.2656 - for (int i = left - 1; ++i < right; a[i] = b[i]);
1.2657 - } else {
1.2658 - b = new double[a.length];
1.2659 - }
1.2660 -
1.2661 - // Merging
1.2662 - for (int last; count > 1; count = last) {
1.2663 - for (int k = (last = 0) + 2; k <= count; k += 2) {
1.2664 - int hi = run[k], mi = run[k - 1];
1.2665 - for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
1.2666 - if (q >= hi || p < mi && a[p] <= a[q]) {
1.2667 - b[i] = a[p++];
1.2668 - } else {
1.2669 - b[i] = a[q++];
1.2670 - }
1.2671 - }
1.2672 - run[++last] = hi;
1.2673 - }
1.2674 - if ((count & 1) != 0) {
1.2675 - for (int i = right, lo = run[count - 1]; --i >= lo;
1.2676 - b[i] = a[i]
1.2677 - );
1.2678 - run[++last] = right;
1.2679 - }
1.2680 - double[] t = a; a = b; b = t;
1.2681 - }
1.2682 - }
1.2683 -
1.2684 - /**
1.2685 - * Sorts the specified range of the array by Dual-Pivot Quicksort.
1.2686 - *
1.2687 - * @param a the array to be sorted
1.2688 - * @param left the index of the first element, inclusive, to be sorted
1.2689 - * @param right the index of the last element, inclusive, to be sorted
1.2690 - * @param leftmost indicates if this part is the leftmost in the range
1.2691 - */
1.2692 - private static void sort(double[] a, int left, int right, boolean leftmost) {
1.2693 - int length = right - left + 1;
1.2694 -
1.2695 - // Use insertion sort on tiny arrays
1.2696 - if (length < INSERTION_SORT_THRESHOLD) {
1.2697 - if (leftmost) {
1.2698 - /*
1.2699 - * Traditional (without sentinel) insertion sort,
1.2700 - * optimized for server VM, is used in case of
1.2701 - * the leftmost part.
1.2702 - */
1.2703 - for (int i = left, j = i; i < right; j = ++i) {
1.2704 - double ai = a[i + 1];
1.2705 - while (ai < a[j]) {
1.2706 - a[j + 1] = a[j];
1.2707 - if (j-- == left) {
1.2708 - break;
1.2709 - }
1.2710 - }
1.2711 - a[j + 1] = ai;
1.2712 - }
1.2713 - } else {
1.2714 - /*
1.2715 - * Skip the longest ascending sequence.
1.2716 - */
1.2717 - do {
1.2718 - if (left >= right) {
1.2719 - return;
1.2720 - }
1.2721 - } while (a[++left] >= a[left - 1]);
1.2722 -
1.2723 - /*
1.2724 - * Every element from adjoining part plays the role
1.2725 - * of sentinel, therefore this allows us to avoid the
1.2726 - * left range check on each iteration. Moreover, we use
1.2727 - * the more optimized algorithm, so called pair insertion
1.2728 - * sort, which is faster (in the context of Quicksort)
1.2729 - * than traditional implementation of insertion sort.
1.2730 - */
1.2731 - for (int k = left; ++left <= right; k = ++left) {
1.2732 - double a1 = a[k], a2 = a[left];
1.2733 -
1.2734 - if (a1 < a2) {
1.2735 - a2 = a1; a1 = a[left];
1.2736 - }
1.2737 - while (a1 < a[--k]) {
1.2738 - a[k + 2] = a[k];
1.2739 - }
1.2740 - a[++k + 1] = a1;
1.2741 -
1.2742 - while (a2 < a[--k]) {
1.2743 - a[k + 1] = a[k];
1.2744 - }
1.2745 - a[k + 1] = a2;
1.2746 - }
1.2747 - double last = a[right];
1.2748 -
1.2749 - while (last < a[--right]) {
1.2750 - a[right + 1] = a[right];
1.2751 - }
1.2752 - a[right + 1] = last;
1.2753 - }
1.2754 - return;
1.2755 - }
1.2756 -
1.2757 - // Inexpensive approximation of length / 7
1.2758 - int seventh = (length >> 3) + (length >> 6) + 1;
1.2759 -
1.2760 - /*
1.2761 - * Sort five evenly spaced elements around (and including) the
1.2762 - * center element in the range. These elements will be used for
1.2763 - * pivot selection as described below. The choice for spacing
1.2764 - * these elements was empirically determined to work well on
1.2765 - * a wide variety of inputs.
1.2766 - */
1.2767 - int e3 = (left + right) >>> 1; // The midpoint
1.2768 - int e2 = e3 - seventh;
1.2769 - int e1 = e2 - seventh;
1.2770 - int e4 = e3 + seventh;
1.2771 - int e5 = e4 + seventh;
1.2772 -
1.2773 - // Sort these elements using insertion sort
1.2774 - if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
1.2775 -
1.2776 - if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
1.2777 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2778 - }
1.2779 - if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
1.2780 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.2781 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2782 - }
1.2783 - }
1.2784 - if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
1.2785 - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
1.2786 - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
1.2787 - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
1.2788 - }
1.2789 - }
1.2790 - }
1.2791 -
1.2792 - // Pointers
1.2793 - int less = left; // The index of the first element of center part
1.2794 - int great = right; // The index before the first element of right part
1.2795 -
1.2796 - if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
1.2797 - /*
1.2798 - * Use the second and fourth of the five sorted elements as pivots.
1.2799 - * These values are inexpensive approximations of the first and
1.2800 - * second terciles of the array. Note that pivot1 <= pivot2.
1.2801 - */
1.2802 - double pivot1 = a[e2];
1.2803 - double pivot2 = a[e4];
1.2804 -
1.2805 - /*
1.2806 - * The first and the last elements to be sorted are moved to the
1.2807 - * locations formerly occupied by the pivots. When partitioning
1.2808 - * is complete, the pivots are swapped back into their final
1.2809 - * positions, and excluded from subsequent sorting.
1.2810 - */
1.2811 - a[e2] = a[left];
1.2812 - a[e4] = a[right];
1.2813 -
1.2814 - /*
1.2815 - * Skip elements, which are less or greater than pivot values.
1.2816 - */
1.2817 - while (a[++less] < pivot1);
1.2818 - while (a[--great] > pivot2);
1.2819 -
1.2820 - /*
1.2821 - * Partitioning:
1.2822 - *
1.2823 - * left part center part right part
1.2824 - * +--------------------------------------------------------------+
1.2825 - * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
1.2826 - * +--------------------------------------------------------------+
1.2827 - * ^ ^ ^
1.2828 - * | | |
1.2829 - * less k great
1.2830 - *
1.2831 - * Invariants:
1.2832 - *
1.2833 - * all in (left, less) < pivot1
1.2834 - * pivot1 <= all in [less, k) <= pivot2
1.2835 - * all in (great, right) > pivot2
1.2836 - *
1.2837 - * Pointer k is the first index of ?-part.
1.2838 - */
1.2839 - outer:
1.2840 - for (int k = less - 1; ++k <= great; ) {
1.2841 - double ak = a[k];
1.2842 - if (ak < pivot1) { // Move a[k] to left part
1.2843 - a[k] = a[less];
1.2844 - /*
1.2845 - * Here and below we use "a[i] = b; i++;" instead
1.2846 - * of "a[i++] = b;" due to performance issue.
1.2847 - */
1.2848 - a[less] = ak;
1.2849 - ++less;
1.2850 - } else if (ak > pivot2) { // Move a[k] to right part
1.2851 - while (a[great] > pivot2) {
1.2852 - if (great-- == k) {
1.2853 - break outer;
1.2854 - }
1.2855 - }
1.2856 - if (a[great] < pivot1) { // a[great] <= pivot2
1.2857 - a[k] = a[less];
1.2858 - a[less] = a[great];
1.2859 - ++less;
1.2860 - } else { // pivot1 <= a[great] <= pivot2
1.2861 - a[k] = a[great];
1.2862 - }
1.2863 - /*
1.2864 - * Here and below we use "a[i] = b; i--;" instead
1.2865 - * of "a[i--] = b;" due to performance issue.
1.2866 - */
1.2867 - a[great] = ak;
1.2868 - --great;
1.2869 - }
1.2870 - }
1.2871 -
1.2872 - // Swap pivots into their final positions
1.2873 - a[left] = a[less - 1]; a[less - 1] = pivot1;
1.2874 - a[right] = a[great + 1]; a[great + 1] = pivot2;
1.2875 -
1.2876 - // Sort left and right parts recursively, excluding known pivots
1.2877 - sort(a, left, less - 2, leftmost);
1.2878 - sort(a, great + 2, right, false);
1.2879 -
1.2880 - /*
1.2881 - * If center part is too large (comprises > 4/7 of the array),
1.2882 - * swap internal pivot values to ends.
1.2883 - */
1.2884 - if (less < e1 && e5 < great) {
1.2885 - /*
1.2886 - * Skip elements, which are equal to pivot values.
1.2887 - */
1.2888 - while (a[less] == pivot1) {
1.2889 - ++less;
1.2890 - }
1.2891 -
1.2892 - while (a[great] == pivot2) {
1.2893 - --great;
1.2894 - }
1.2895 -
1.2896 - /*
1.2897 - * Partitioning:
1.2898 - *
1.2899 - * left part center part right part
1.2900 - * +----------------------------------------------------------+
1.2901 - * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
1.2902 - * +----------------------------------------------------------+
1.2903 - * ^ ^ ^
1.2904 - * | | |
1.2905 - * less k great
1.2906 - *
1.2907 - * Invariants:
1.2908 - *
1.2909 - * all in (*, less) == pivot1
1.2910 - * pivot1 < all in [less, k) < pivot2
1.2911 - * all in (great, *) == pivot2
1.2912 - *
1.2913 - * Pointer k is the first index of ?-part.
1.2914 - */
1.2915 - outer:
1.2916 - for (int k = less - 1; ++k <= great; ) {
1.2917 - double ak = a[k];
1.2918 - if (ak == pivot1) { // Move a[k] to left part
1.2919 - a[k] = a[less];
1.2920 - a[less] = ak;
1.2921 - ++less;
1.2922 - } else if (ak == pivot2) { // Move a[k] to right part
1.2923 - while (a[great] == pivot2) {
1.2924 - if (great-- == k) {
1.2925 - break outer;
1.2926 - }
1.2927 - }
1.2928 - if (a[great] == pivot1) { // a[great] < pivot2
1.2929 - a[k] = a[less];
1.2930 - /*
1.2931 - * Even though a[great] equals to pivot1, the
1.2932 - * assignment a[less] = pivot1 may be incorrect,
1.2933 - * if a[great] and pivot1 are floating-point zeros
1.2934 - * of different signs. Therefore in float and
1.2935 - * double sorting methods we have to use more
1.2936 - * accurate assignment a[less] = a[great].
1.2937 - */
1.2938 - a[less] = a[great];
1.2939 - ++less;
1.2940 - } else { // pivot1 < a[great] < pivot2
1.2941 - a[k] = a[great];
1.2942 - }
1.2943 - a[great] = ak;
1.2944 - --great;
1.2945 - }
1.2946 - }
1.2947 - }
1.2948 -
1.2949 - // Sort center part recursively
1.2950 - sort(a, less, great, false);
1.2951 -
1.2952 - } else { // Partitioning with one pivot
1.2953 - /*
1.2954 - * Use the third of the five sorted elements as pivot.
1.2955 - * This value is inexpensive approximation of the median.
1.2956 - */
1.2957 - double pivot = a[e3];
1.2958 -
1.2959 - /*
1.2960 - * Partitioning degenerates to the traditional 3-way
1.2961 - * (or "Dutch National Flag") schema:
1.2962 - *
1.2963 - * left part center part right part
1.2964 - * +-------------------------------------------------+
1.2965 - * | < pivot | == pivot | ? | > pivot |
1.2966 - * +-------------------------------------------------+
1.2967 - * ^ ^ ^
1.2968 - * | | |
1.2969 - * less k great
1.2970 - *
1.2971 - * Invariants:
1.2972 - *
1.2973 - * all in (left, less) < pivot
1.2974 - * all in [less, k) == pivot
1.2975 - * all in (great, right) > pivot
1.2976 - *
1.2977 - * Pointer k is the first index of ?-part.
1.2978 - */
1.2979 - for (int k = less; k <= great; ++k) {
1.2980 - if (a[k] == pivot) {
1.2981 - continue;
1.2982 - }
1.2983 - double ak = a[k];
1.2984 - if (ak < pivot) { // Move a[k] to left part
1.2985 - a[k] = a[less];
1.2986 - a[less] = ak;
1.2987 - ++less;
1.2988 - } else { // a[k] > pivot - Move a[k] to right part
1.2989 - while (a[great] > pivot) {
1.2990 - --great;
1.2991 - }
1.2992 - if (a[great] < pivot) { // a[great] <= pivot
1.2993 - a[k] = a[less];
1.2994 - a[less] = a[great];
1.2995 - ++less;
1.2996 - } else { // a[great] == pivot
1.2997 - /*
1.2998 - * Even though a[great] equals to pivot, the
1.2999 - * assignment a[k] = pivot may be incorrect,
1.3000 - * if a[great] and pivot are floating-point
1.3001 - * zeros of different signs. Therefore in float
1.3002 - * and double sorting methods we have to use
1.3003 - * more accurate assignment a[k] = a[great].
1.3004 - */
1.3005 - a[k] = a[great];
1.3006 - }
1.3007 - a[great] = ak;
1.3008 - --great;
1.3009 - }
1.3010 - }
1.3011 -
1.3012 - /*
1.3013 - * Sort left and right parts recursively.
1.3014 - * All elements from center part are equal
1.3015 - * and, therefore, already sorted.
1.3016 - */
1.3017 - sort(a, left, less - 1, leftmost);
1.3018 - sort(a, great + 1, right, false);
1.3019 - }
1.3020 - }
1.3021 -}