1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/DualPivotQuicksort.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,3018 @@
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 +}