1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/lang/SafeVarargs.java Wed Jan 23 23:19:47 2013 +0100
1.3 @@ -0,0 +1,91 @@
1.4 +/*
1.5 + * Copyright (c) 2010, 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.lang;
1.30 +
1.31 +import java.lang.annotation.*;
1.32 +
1.33 +/**
1.34 + * A programmer assertion that the body of the annotated method or
1.35 + * constructor does not perform potentially unsafe operations on its
1.36 + * varargs parameter. Applying this annotation to a method or
1.37 + * constructor suppresses unchecked warnings about a
1.38 + * <i>non-reifiable</i> variable arity (vararg) type and suppresses
1.39 + * unchecked warnings about parameterized array creation at call
1.40 + * sites.
1.41 + *
1.42 + * <p> In addition to the usage restrictions imposed by its {@link
1.43 + * Target @Target} meta-annotation, compilers are required to implement
1.44 + * additional usage restrictions on this annotation type; it is a
1.45 + * compile-time error if a method or constructor declaration is
1.46 + * annotated with a {@code @SafeVarargs} annotation, and either:
1.47 + * <ul>
1.48 + * <li> the declaration is a fixed arity method or constructor
1.49 + *
1.50 + * <li> the declaration is a variable arity method that is neither
1.51 + * {@code static} nor {@code final}.
1.52 + *
1.53 + * </ul>
1.54 + *
1.55 + * <p> Compilers are encouraged to issue warnings when this annotation
1.56 + * type is applied to a method or constructor declaration where:
1.57 + *
1.58 + * <ul>
1.59 + *
1.60 + * <li> The variable arity parameter has a reifiable element type,
1.61 + * which includes primitive types, {@code Object}, and {@code String}.
1.62 + * (The unchecked warnings this annotation type suppresses already do
1.63 + * not occur for a reifiable element type.)
1.64 + *
1.65 + * <li> The body of the method or constructor declaration performs
1.66 + * potentially unsafe operations, such as an assignment to an element
1.67 + * of the variable arity parameter's array that generates an unchecked
1.68 + * warning. Some unsafe operations do not trigger an unchecked
1.69 + * warning. For example, the aliasing in
1.70 + *
1.71 + * <blockquote><pre>
1.72 + * @SafeVarargs // Not actually safe!
1.73 + * static void m(List<String>... stringLists) {
1.74 + * Object[] array = stringLists;
1.75 + * List<Integer> tmpList = Arrays.asList(42);
1.76 + * array[0] = tmpList; // Semantically invalid, but compiles without warnings
1.77 + * String s = stringLists[0].get(0); // Oh no, ClassCastException at runtime!
1.78 + * }
1.79 + * </pre></blockquote>
1.80 + *
1.81 + * leads to a {@code ClassCastException} at runtime.
1.82 + *
1.83 + * <p>Future versions of the platform may mandate compiler errors for
1.84 + * such unsafe operations.
1.85 + *
1.86 + * </ul>
1.87 + *
1.88 + * @jls 4.7 Reifiable Types
1.89 + * @jls 8.4.1 Formal Parameters
1.90 + */
1.91 +@Documented
1.92 +@Retention(RetentionPolicy.RUNTIME)
1.93 +@Target({ElementType.CONSTRUCTOR, ElementType.METHOD})
1.94 +public @interface SafeVarargs {}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/emul/compact/src/main/java/java/util/ComparableTimSort.java Wed Jan 23 23:19:47 2013 +0100
2.3 @@ -0,0 +1,895 @@
2.4 +/*
2.5 + * Copyright 2009 Google Inc. All Rights Reserved.
2.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
2.7 + *
2.8 + * This code is free software; you can redistribute it and/or modify it
2.9 + * under the terms of the GNU General Public License version 2 only, as
2.10 + * published by the Free Software Foundation. Oracle designates this
2.11 + * particular file as subject to the "Classpath" exception as provided
2.12 + * by Oracle in the LICENSE file that accompanied this code.
2.13 + *
2.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
2.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
2.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
2.17 + * version 2 for more details (a copy is included in the LICENSE file that
2.18 + * accompanied this code).
2.19 + *
2.20 + * You should have received a copy of the GNU General Public License version
2.21 + * 2 along with this work; if not, write to the Free Software Foundation,
2.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
2.23 + *
2.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2.25 + * or visit www.oracle.com if you need additional information or have any
2.26 + * questions.
2.27 + */
2.28 +
2.29 +package java.util;
2.30 +
2.31 +/**
2.32 + * This is a near duplicate of {@link TimSort}, modified for use with
2.33 + * arrays of objects that implement {@link Comparable}, instead of using
2.34 + * explicit comparators.
2.35 + *
2.36 + * <p>If you are using an optimizing VM, you may find that ComparableTimSort
2.37 + * offers no performance benefit over TimSort in conjunction with a
2.38 + * comparator that simply returns {@code ((Comparable)first).compareTo(Second)}.
2.39 + * If this is the case, you are better off deleting ComparableTimSort to
2.40 + * eliminate the code duplication. (See Arrays.java for details.)
2.41 + *
2.42 + * @author Josh Bloch
2.43 + */
2.44 +class ComparableTimSort {
2.45 + /**
2.46 + * This is the minimum sized sequence that will be merged. Shorter
2.47 + * sequences will be lengthened by calling binarySort. If the entire
2.48 + * array is less than this length, no merges will be performed.
2.49 + *
2.50 + * This constant should be a power of two. It was 64 in Tim Peter's C
2.51 + * implementation, but 32 was empirically determined to work better in
2.52 + * this implementation. In the unlikely event that you set this constant
2.53 + * to be a number that's not a power of two, you'll need to change the
2.54 + * {@link #minRunLength} computation.
2.55 + *
2.56 + * If you decrease this constant, you must change the stackLen
2.57 + * computation in the TimSort constructor, or you risk an
2.58 + * ArrayOutOfBounds exception. See listsort.txt for a discussion
2.59 + * of the minimum stack length required as a function of the length
2.60 + * of the array being sorted and the minimum merge sequence length.
2.61 + */
2.62 + private static final int MIN_MERGE = 32;
2.63 +
2.64 + /**
2.65 + * The array being sorted.
2.66 + */
2.67 + private final Object[] a;
2.68 +
2.69 + /**
2.70 + * When we get into galloping mode, we stay there until both runs win less
2.71 + * often than MIN_GALLOP consecutive times.
2.72 + */
2.73 + private static final int MIN_GALLOP = 7;
2.74 +
2.75 + /**
2.76 + * This controls when we get *into* galloping mode. It is initialized
2.77 + * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
2.78 + * random data, and lower for highly structured data.
2.79 + */
2.80 + private int minGallop = MIN_GALLOP;
2.81 +
2.82 + /**
2.83 + * Maximum initial size of tmp array, which is used for merging. The array
2.84 + * can grow to accommodate demand.
2.85 + *
2.86 + * Unlike Tim's original C version, we do not allocate this much storage
2.87 + * when sorting smaller arrays. This change was required for performance.
2.88 + */
2.89 + private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
2.90 +
2.91 + /**
2.92 + * Temp storage for merges.
2.93 + */
2.94 + private Object[] tmp;
2.95 +
2.96 + /**
2.97 + * A stack of pending runs yet to be merged. Run i starts at
2.98 + * address base[i] and extends for len[i] elements. It's always
2.99 + * true (so long as the indices are in bounds) that:
2.100 + *
2.101 + * runBase[i] + runLen[i] == runBase[i + 1]
2.102 + *
2.103 + * so we could cut the storage for this, but it's a minor amount,
2.104 + * and keeping all the info explicit simplifies the code.
2.105 + */
2.106 + private int stackSize = 0; // Number of pending runs on stack
2.107 + private final int[] runBase;
2.108 + private final int[] runLen;
2.109 +
2.110 + /**
2.111 + * Creates a TimSort instance to maintain the state of an ongoing sort.
2.112 + *
2.113 + * @param a the array to be sorted
2.114 + */
2.115 + private ComparableTimSort(Object[] a) {
2.116 + this.a = a;
2.117 +
2.118 + // Allocate temp storage (which may be increased later if necessary)
2.119 + int len = a.length;
2.120 + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
2.121 + Object[] newArray = new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
2.122 + len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
2.123 + tmp = newArray;
2.124 +
2.125 + /*
2.126 + * Allocate runs-to-be-merged stack (which cannot be expanded). The
2.127 + * stack length requirements are described in listsort.txt. The C
2.128 + * version always uses the same stack length (85), but this was
2.129 + * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
2.130 + * 100 elements) in Java. Therefore, we use smaller (but sufficiently
2.131 + * large) stack lengths for smaller arrays. The "magic numbers" in the
2.132 + * computation below must be changed if MIN_MERGE is decreased. See
2.133 + * the MIN_MERGE declaration above for more information.
2.134 + */
2.135 + int stackLen = (len < 120 ? 5 :
2.136 + len < 1542 ? 10 :
2.137 + len < 119151 ? 19 : 40);
2.138 + runBase = new int[stackLen];
2.139 + runLen = new int[stackLen];
2.140 + }
2.141 +
2.142 + /*
2.143 + * The next two methods (which are package private and static) constitute
2.144 + * the entire API of this class. Each of these methods obeys the contract
2.145 + * of the public method with the same signature in java.util.Arrays.
2.146 + */
2.147 +
2.148 + static void sort(Object[] a) {
2.149 + sort(a, 0, a.length);
2.150 + }
2.151 +
2.152 + static void sort(Object[] a, int lo, int hi) {
2.153 + rangeCheck(a.length, lo, hi);
2.154 + int nRemaining = hi - lo;
2.155 + if (nRemaining < 2)
2.156 + return; // Arrays of size 0 and 1 are always sorted
2.157 +
2.158 + // If array is small, do a "mini-TimSort" with no merges
2.159 + if (nRemaining < MIN_MERGE) {
2.160 + int initRunLen = countRunAndMakeAscending(a, lo, hi);
2.161 + binarySort(a, lo, hi, lo + initRunLen);
2.162 + return;
2.163 + }
2.164 +
2.165 + /**
2.166 + * March over the array once, left to right, finding natural runs,
2.167 + * extending short natural runs to minRun elements, and merging runs
2.168 + * to maintain stack invariant.
2.169 + */
2.170 + ComparableTimSort ts = new ComparableTimSort(a);
2.171 + int minRun = minRunLength(nRemaining);
2.172 + do {
2.173 + // Identify next run
2.174 + int runLen = countRunAndMakeAscending(a, lo, hi);
2.175 +
2.176 + // If run is short, extend to min(minRun, nRemaining)
2.177 + if (runLen < minRun) {
2.178 + int force = nRemaining <= minRun ? nRemaining : minRun;
2.179 + binarySort(a, lo, lo + force, lo + runLen);
2.180 + runLen = force;
2.181 + }
2.182 +
2.183 + // Push run onto pending-run stack, and maybe merge
2.184 + ts.pushRun(lo, runLen);
2.185 + ts.mergeCollapse();
2.186 +
2.187 + // Advance to find next run
2.188 + lo += runLen;
2.189 + nRemaining -= runLen;
2.190 + } while (nRemaining != 0);
2.191 +
2.192 + // Merge all remaining runs to complete sort
2.193 + assert lo == hi;
2.194 + ts.mergeForceCollapse();
2.195 + assert ts.stackSize == 1;
2.196 + }
2.197 +
2.198 + /**
2.199 + * Sorts the specified portion of the specified array using a binary
2.200 + * insertion sort. This is the best method for sorting small numbers
2.201 + * of elements. It requires O(n log n) compares, but O(n^2) data
2.202 + * movement (worst case).
2.203 + *
2.204 + * If the initial part of the specified range is already sorted,
2.205 + * this method can take advantage of it: the method assumes that the
2.206 + * elements from index {@code lo}, inclusive, to {@code start},
2.207 + * exclusive are already sorted.
2.208 + *
2.209 + * @param a the array in which a range is to be sorted
2.210 + * @param lo the index of the first element in the range to be sorted
2.211 + * @param hi the index after the last element in the range to be sorted
2.212 + * @param start the index of the first element in the range that is
2.213 + * not already known to be sorted ({@code lo <= start <= hi})
2.214 + */
2.215 + @SuppressWarnings("fallthrough")
2.216 + private static void binarySort(Object[] a, int lo, int hi, int start) {
2.217 + assert lo <= start && start <= hi;
2.218 + if (start == lo)
2.219 + start++;
2.220 + for ( ; start < hi; start++) {
2.221 + @SuppressWarnings("unchecked")
2.222 + Comparable<Object> pivot = (Comparable) a[start];
2.223 +
2.224 + // Set left (and right) to the index where a[start] (pivot) belongs
2.225 + int left = lo;
2.226 + int right = start;
2.227 + assert left <= right;
2.228 + /*
2.229 + * Invariants:
2.230 + * pivot >= all in [lo, left).
2.231 + * pivot < all in [right, start).
2.232 + */
2.233 + while (left < right) {
2.234 + int mid = (left + right) >>> 1;
2.235 + if (pivot.compareTo(a[mid]) < 0)
2.236 + right = mid;
2.237 + else
2.238 + left = mid + 1;
2.239 + }
2.240 + assert left == right;
2.241 +
2.242 + /*
2.243 + * The invariants still hold: pivot >= all in [lo, left) and
2.244 + * pivot < all in [left, start), so pivot belongs at left. Note
2.245 + * that if there are elements equal to pivot, left points to the
2.246 + * first slot after them -- that's why this sort is stable.
2.247 + * Slide elements over to make room for pivot.
2.248 + */
2.249 + int n = start - left; // The number of elements to move
2.250 + // Switch is just an optimization for arraycopy in default case
2.251 + switch (n) {
2.252 + case 2: a[left + 2] = a[left + 1];
2.253 + case 1: a[left + 1] = a[left];
2.254 + break;
2.255 + default: System.arraycopy(a, left, a, left + 1, n);
2.256 + }
2.257 + a[left] = pivot;
2.258 + }
2.259 + }
2.260 +
2.261 + /**
2.262 + * Returns the length of the run beginning at the specified position in
2.263 + * the specified array and reverses the run if it is descending (ensuring
2.264 + * that the run will always be ascending when the method returns).
2.265 + *
2.266 + * A run is the longest ascending sequence with:
2.267 + *
2.268 + * a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
2.269 + *
2.270 + * or the longest descending sequence with:
2.271 + *
2.272 + * a[lo] > a[lo + 1] > a[lo + 2] > ...
2.273 + *
2.274 + * For its intended use in a stable mergesort, the strictness of the
2.275 + * definition of "descending" is needed so that the call can safely
2.276 + * reverse a descending sequence without violating stability.
2.277 + *
2.278 + * @param a the array in which a run is to be counted and possibly reversed
2.279 + * @param lo index of the first element in the run
2.280 + * @param hi index after the last element that may be contained in the run.
2.281 + It is required that {@code lo < hi}.
2.282 + * @return the length of the run beginning at the specified position in
2.283 + * the specified array
2.284 + */
2.285 + @SuppressWarnings("unchecked")
2.286 + private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
2.287 + assert lo < hi;
2.288 + int runHi = lo + 1;
2.289 + if (runHi == hi)
2.290 + return 1;
2.291 +
2.292 + // Find end of run, and reverse range if descending
2.293 + if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
2.294 + while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
2.295 + runHi++;
2.296 + reverseRange(a, lo, runHi);
2.297 + } else { // Ascending
2.298 + while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
2.299 + runHi++;
2.300 + }
2.301 +
2.302 + return runHi - lo;
2.303 + }
2.304 +
2.305 + /**
2.306 + * Reverse the specified range of the specified array.
2.307 + *
2.308 + * @param a the array in which a range is to be reversed
2.309 + * @param lo the index of the first element in the range to be reversed
2.310 + * @param hi the index after the last element in the range to be reversed
2.311 + */
2.312 + private static void reverseRange(Object[] a, int lo, int hi) {
2.313 + hi--;
2.314 + while (lo < hi) {
2.315 + Object t = a[lo];
2.316 + a[lo++] = a[hi];
2.317 + a[hi--] = t;
2.318 + }
2.319 + }
2.320 +
2.321 + /**
2.322 + * Returns the minimum acceptable run length for an array of the specified
2.323 + * length. Natural runs shorter than this will be extended with
2.324 + * {@link #binarySort}.
2.325 + *
2.326 + * Roughly speaking, the computation is:
2.327 + *
2.328 + * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
2.329 + * Else if n is an exact power of 2, return MIN_MERGE/2.
2.330 + * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
2.331 + * is close to, but strictly less than, an exact power of 2.
2.332 + *
2.333 + * For the rationale, see listsort.txt.
2.334 + *
2.335 + * @param n the length of the array to be sorted
2.336 + * @return the length of the minimum run to be merged
2.337 + */
2.338 + private static int minRunLength(int n) {
2.339 + assert n >= 0;
2.340 + int r = 0; // Becomes 1 if any 1 bits are shifted off
2.341 + while (n >= MIN_MERGE) {
2.342 + r |= (n & 1);
2.343 + n >>= 1;
2.344 + }
2.345 + return n + r;
2.346 + }
2.347 +
2.348 + /**
2.349 + * Pushes the specified run onto the pending-run stack.
2.350 + *
2.351 + * @param runBase index of the first element in the run
2.352 + * @param runLen the number of elements in the run
2.353 + */
2.354 + private void pushRun(int runBase, int runLen) {
2.355 + this.runBase[stackSize] = runBase;
2.356 + this.runLen[stackSize] = runLen;
2.357 + stackSize++;
2.358 + }
2.359 +
2.360 + /**
2.361 + * Examines the stack of runs waiting to be merged and merges adjacent runs
2.362 + * until the stack invariants are reestablished:
2.363 + *
2.364 + * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
2.365 + * 2. runLen[i - 2] > runLen[i - 1]
2.366 + *
2.367 + * This method is called each time a new run is pushed onto the stack,
2.368 + * so the invariants are guaranteed to hold for i < stackSize upon
2.369 + * entry to the method.
2.370 + */
2.371 + private void mergeCollapse() {
2.372 + while (stackSize > 1) {
2.373 + int n = stackSize - 2;
2.374 + if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
2.375 + if (runLen[n - 1] < runLen[n + 1])
2.376 + n--;
2.377 + mergeAt(n);
2.378 + } else if (runLen[n] <= runLen[n + 1]) {
2.379 + mergeAt(n);
2.380 + } else {
2.381 + break; // Invariant is established
2.382 + }
2.383 + }
2.384 + }
2.385 +
2.386 + /**
2.387 + * Merges all runs on the stack until only one remains. This method is
2.388 + * called once, to complete the sort.
2.389 + */
2.390 + private void mergeForceCollapse() {
2.391 + while (stackSize > 1) {
2.392 + int n = stackSize - 2;
2.393 + if (n > 0 && runLen[n - 1] < runLen[n + 1])
2.394 + n--;
2.395 + mergeAt(n);
2.396 + }
2.397 + }
2.398 +
2.399 + /**
2.400 + * Merges the two runs at stack indices i and i+1. Run i must be
2.401 + * the penultimate or antepenultimate run on the stack. In other words,
2.402 + * i must be equal to stackSize-2 or stackSize-3.
2.403 + *
2.404 + * @param i stack index of the first of the two runs to merge
2.405 + */
2.406 + @SuppressWarnings("unchecked")
2.407 + private void mergeAt(int i) {
2.408 + assert stackSize >= 2;
2.409 + assert i >= 0;
2.410 + assert i == stackSize - 2 || i == stackSize - 3;
2.411 +
2.412 + int base1 = runBase[i];
2.413 + int len1 = runLen[i];
2.414 + int base2 = runBase[i + 1];
2.415 + int len2 = runLen[i + 1];
2.416 + assert len1 > 0 && len2 > 0;
2.417 + assert base1 + len1 == base2;
2.418 +
2.419 + /*
2.420 + * Record the length of the combined runs; if i is the 3rd-last
2.421 + * run now, also slide over the last run (which isn't involved
2.422 + * in this merge). The current run (i+1) goes away in any case.
2.423 + */
2.424 + runLen[i] = len1 + len2;
2.425 + if (i == stackSize - 3) {
2.426 + runBase[i + 1] = runBase[i + 2];
2.427 + runLen[i + 1] = runLen[i + 2];
2.428 + }
2.429 + stackSize--;
2.430 +
2.431 + /*
2.432 + * Find where the first element of run2 goes in run1. Prior elements
2.433 + * in run1 can be ignored (because they're already in place).
2.434 + */
2.435 + int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0);
2.436 + assert k >= 0;
2.437 + base1 += k;
2.438 + len1 -= k;
2.439 + if (len1 == 0)
2.440 + return;
2.441 +
2.442 + /*
2.443 + * Find where the last element of run1 goes in run2. Subsequent elements
2.444 + * in run2 can be ignored (because they're already in place).
2.445 + */
2.446 + len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a,
2.447 + base2, len2, len2 - 1);
2.448 + assert len2 >= 0;
2.449 + if (len2 == 0)
2.450 + return;
2.451 +
2.452 + // Merge remaining runs, using tmp array with min(len1, len2) elements
2.453 + if (len1 <= len2)
2.454 + mergeLo(base1, len1, base2, len2);
2.455 + else
2.456 + mergeHi(base1, len1, base2, len2);
2.457 + }
2.458 +
2.459 + /**
2.460 + * Locates the position at which to insert the specified key into the
2.461 + * specified sorted range; if the range contains an element equal to key,
2.462 + * returns the index of the leftmost equal element.
2.463 + *
2.464 + * @param key the key whose insertion point to search for
2.465 + * @param a the array in which to search
2.466 + * @param base the index of the first element in the range
2.467 + * @param len the length of the range; must be > 0
2.468 + * @param hint the index at which to begin the search, 0 <= hint < n.
2.469 + * The closer hint is to the result, the faster this method will run.
2.470 + * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
2.471 + * pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
2.472 + * In other words, key belongs at index b + k; or in other words,
2.473 + * the first k elements of a should precede key, and the last n - k
2.474 + * should follow it.
2.475 + */
2.476 + private static int gallopLeft(Comparable<Object> key, Object[] a,
2.477 + int base, int len, int hint) {
2.478 + assert len > 0 && hint >= 0 && hint < len;
2.479 +
2.480 + int lastOfs = 0;
2.481 + int ofs = 1;
2.482 + if (key.compareTo(a[base + hint]) > 0) {
2.483 + // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
2.484 + int maxOfs = len - hint;
2.485 + while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) > 0) {
2.486 + lastOfs = ofs;
2.487 + ofs = (ofs << 1) + 1;
2.488 + if (ofs <= 0) // int overflow
2.489 + ofs = maxOfs;
2.490 + }
2.491 + if (ofs > maxOfs)
2.492 + ofs = maxOfs;
2.493 +
2.494 + // Make offsets relative to base
2.495 + lastOfs += hint;
2.496 + ofs += hint;
2.497 + } else { // key <= a[base + hint]
2.498 + // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
2.499 + final int maxOfs = hint + 1;
2.500 + while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) <= 0) {
2.501 + lastOfs = ofs;
2.502 + ofs = (ofs << 1) + 1;
2.503 + if (ofs <= 0) // int overflow
2.504 + ofs = maxOfs;
2.505 + }
2.506 + if (ofs > maxOfs)
2.507 + ofs = maxOfs;
2.508 +
2.509 + // Make offsets relative to base
2.510 + int tmp = lastOfs;
2.511 + lastOfs = hint - ofs;
2.512 + ofs = hint - tmp;
2.513 + }
2.514 + assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
2.515 +
2.516 + /*
2.517 + * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
2.518 + * to the right of lastOfs but no farther right than ofs. Do a binary
2.519 + * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
2.520 + */
2.521 + lastOfs++;
2.522 + while (lastOfs < ofs) {
2.523 + int m = lastOfs + ((ofs - lastOfs) >>> 1);
2.524 +
2.525 + if (key.compareTo(a[base + m]) > 0)
2.526 + lastOfs = m + 1; // a[base + m] < key
2.527 + else
2.528 + ofs = m; // key <= a[base + m]
2.529 + }
2.530 + assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs]
2.531 + return ofs;
2.532 + }
2.533 +
2.534 + /**
2.535 + * Like gallopLeft, except that if the range contains an element equal to
2.536 + * key, gallopRight returns the index after the rightmost equal element.
2.537 + *
2.538 + * @param key the key whose insertion point to search for
2.539 + * @param a the array in which to search
2.540 + * @param base the index of the first element in the range
2.541 + * @param len the length of the range; must be > 0
2.542 + * @param hint the index at which to begin the search, 0 <= hint < n.
2.543 + * The closer hint is to the result, the faster this method will run.
2.544 + * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
2.545 + */
2.546 + private static int gallopRight(Comparable<Object> key, Object[] a,
2.547 + int base, int len, int hint) {
2.548 + assert len > 0 && hint >= 0 && hint < len;
2.549 +
2.550 + int ofs = 1;
2.551 + int lastOfs = 0;
2.552 + if (key.compareTo(a[base + hint]) < 0) {
2.553 + // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
2.554 + int maxOfs = hint + 1;
2.555 + while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) < 0) {
2.556 + lastOfs = ofs;
2.557 + ofs = (ofs << 1) + 1;
2.558 + if (ofs <= 0) // int overflow
2.559 + ofs = maxOfs;
2.560 + }
2.561 + if (ofs > maxOfs)
2.562 + ofs = maxOfs;
2.563 +
2.564 + // Make offsets relative to b
2.565 + int tmp = lastOfs;
2.566 + lastOfs = hint - ofs;
2.567 + ofs = hint - tmp;
2.568 + } else { // a[b + hint] <= key
2.569 + // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
2.570 + int maxOfs = len - hint;
2.571 + while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) >= 0) {
2.572 + lastOfs = ofs;
2.573 + ofs = (ofs << 1) + 1;
2.574 + if (ofs <= 0) // int overflow
2.575 + ofs = maxOfs;
2.576 + }
2.577 + if (ofs > maxOfs)
2.578 + ofs = maxOfs;
2.579 +
2.580 + // Make offsets relative to b
2.581 + lastOfs += hint;
2.582 + ofs += hint;
2.583 + }
2.584 + assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
2.585 +
2.586 + /*
2.587 + * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
2.588 + * the right of lastOfs but no farther right than ofs. Do a binary
2.589 + * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
2.590 + */
2.591 + lastOfs++;
2.592 + while (lastOfs < ofs) {
2.593 + int m = lastOfs + ((ofs - lastOfs) >>> 1);
2.594 +
2.595 + if (key.compareTo(a[base + m]) < 0)
2.596 + ofs = m; // key < a[b + m]
2.597 + else
2.598 + lastOfs = m + 1; // a[b + m] <= key
2.599 + }
2.600 + assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
2.601 + return ofs;
2.602 + }
2.603 +
2.604 + /**
2.605 + * Merges two adjacent runs in place, in a stable fashion. The first
2.606 + * element of the first run must be greater than the first element of the
2.607 + * second run (a[base1] > a[base2]), and the last element of the first run
2.608 + * (a[base1 + len1-1]) must be greater than all elements of the second run.
2.609 + *
2.610 + * For performance, this method should be called only when len1 <= len2;
2.611 + * its twin, mergeHi should be called if len1 >= len2. (Either method
2.612 + * may be called if len1 == len2.)
2.613 + *
2.614 + * @param base1 index of first element in first run to be merged
2.615 + * @param len1 length of first run to be merged (must be > 0)
2.616 + * @param base2 index of first element in second run to be merged
2.617 + * (must be aBase + aLen)
2.618 + * @param len2 length of second run to be merged (must be > 0)
2.619 + */
2.620 + @SuppressWarnings("unchecked")
2.621 + private void mergeLo(int base1, int len1, int base2, int len2) {
2.622 + assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
2.623 +
2.624 + // Copy first run into temp array
2.625 + Object[] a = this.a; // For performance
2.626 + Object[] tmp = ensureCapacity(len1);
2.627 + System.arraycopy(a, base1, tmp, 0, len1);
2.628 +
2.629 + int cursor1 = 0; // Indexes into tmp array
2.630 + int cursor2 = base2; // Indexes int a
2.631 + int dest = base1; // Indexes int a
2.632 +
2.633 + // Move first element of second run and deal with degenerate cases
2.634 + a[dest++] = a[cursor2++];
2.635 + if (--len2 == 0) {
2.636 + System.arraycopy(tmp, cursor1, a, dest, len1);
2.637 + return;
2.638 + }
2.639 + if (len1 == 1) {
2.640 + System.arraycopy(a, cursor2, a, dest, len2);
2.641 + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
2.642 + return;
2.643 + }
2.644 +
2.645 + int minGallop = this.minGallop; // Use local variable for performance
2.646 + outer:
2.647 + while (true) {
2.648 + int count1 = 0; // Number of times in a row that first run won
2.649 + int count2 = 0; // Number of times in a row that second run won
2.650 +
2.651 + /*
2.652 + * Do the straightforward thing until (if ever) one run starts
2.653 + * winning consistently.
2.654 + */
2.655 + do {
2.656 + assert len1 > 1 && len2 > 0;
2.657 + if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) {
2.658 + a[dest++] = a[cursor2++];
2.659 + count2++;
2.660 + count1 = 0;
2.661 + if (--len2 == 0)
2.662 + break outer;
2.663 + } else {
2.664 + a[dest++] = tmp[cursor1++];
2.665 + count1++;
2.666 + count2 = 0;
2.667 + if (--len1 == 1)
2.668 + break outer;
2.669 + }
2.670 + } while ((count1 | count2) < minGallop);
2.671 +
2.672 + /*
2.673 + * One run is winning so consistently that galloping may be a
2.674 + * huge win. So try that, and continue galloping until (if ever)
2.675 + * neither run appears to be winning consistently anymore.
2.676 + */
2.677 + do {
2.678 + assert len1 > 1 && len2 > 0;
2.679 + count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0);
2.680 + if (count1 != 0) {
2.681 + System.arraycopy(tmp, cursor1, a, dest, count1);
2.682 + dest += count1;
2.683 + cursor1 += count1;
2.684 + len1 -= count1;
2.685 + if (len1 <= 1) // len1 == 1 || len1 == 0
2.686 + break outer;
2.687 + }
2.688 + a[dest++] = a[cursor2++];
2.689 + if (--len2 == 0)
2.690 + break outer;
2.691 +
2.692 + count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0);
2.693 + if (count2 != 0) {
2.694 + System.arraycopy(a, cursor2, a, dest, count2);
2.695 + dest += count2;
2.696 + cursor2 += count2;
2.697 + len2 -= count2;
2.698 + if (len2 == 0)
2.699 + break outer;
2.700 + }
2.701 + a[dest++] = tmp[cursor1++];
2.702 + if (--len1 == 1)
2.703 + break outer;
2.704 + minGallop--;
2.705 + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
2.706 + if (minGallop < 0)
2.707 + minGallop = 0;
2.708 + minGallop += 2; // Penalize for leaving gallop mode
2.709 + } // End of "outer" loop
2.710 + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
2.711 +
2.712 + if (len1 == 1) {
2.713 + assert len2 > 0;
2.714 + System.arraycopy(a, cursor2, a, dest, len2);
2.715 + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
2.716 + } else if (len1 == 0) {
2.717 + throw new IllegalArgumentException(
2.718 + "Comparison method violates its general contract!");
2.719 + } else {
2.720 + assert len2 == 0;
2.721 + assert len1 > 1;
2.722 + System.arraycopy(tmp, cursor1, a, dest, len1);
2.723 + }
2.724 + }
2.725 +
2.726 + /**
2.727 + * Like mergeLo, except that this method should be called only if
2.728 + * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
2.729 + * may be called if len1 == len2.)
2.730 + *
2.731 + * @param base1 index of first element in first run to be merged
2.732 + * @param len1 length of first run to be merged (must be > 0)
2.733 + * @param base2 index of first element in second run to be merged
2.734 + * (must be aBase + aLen)
2.735 + * @param len2 length of second run to be merged (must be > 0)
2.736 + */
2.737 + @SuppressWarnings("unchecked")
2.738 + private void mergeHi(int base1, int len1, int base2, int len2) {
2.739 + assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
2.740 +
2.741 + // Copy second run into temp array
2.742 + Object[] a = this.a; // For performance
2.743 + Object[] tmp = ensureCapacity(len2);
2.744 + System.arraycopy(a, base2, tmp, 0, len2);
2.745 +
2.746 + int cursor1 = base1 + len1 - 1; // Indexes into a
2.747 + int cursor2 = len2 - 1; // Indexes into tmp array
2.748 + int dest = base2 + len2 - 1; // Indexes into a
2.749 +
2.750 + // Move last element of first run and deal with degenerate cases
2.751 + a[dest--] = a[cursor1--];
2.752 + if (--len1 == 0) {
2.753 + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
2.754 + return;
2.755 + }
2.756 + if (len2 == 1) {
2.757 + dest -= len1;
2.758 + cursor1 -= len1;
2.759 + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
2.760 + a[dest] = tmp[cursor2];
2.761 + return;
2.762 + }
2.763 +
2.764 + int minGallop = this.minGallop; // Use local variable for performance
2.765 + outer:
2.766 + while (true) {
2.767 + int count1 = 0; // Number of times in a row that first run won
2.768 + int count2 = 0; // Number of times in a row that second run won
2.769 +
2.770 + /*
2.771 + * Do the straightforward thing until (if ever) one run
2.772 + * appears to win consistently.
2.773 + */
2.774 + do {
2.775 + assert len1 > 0 && len2 > 1;
2.776 + if (((Comparable) tmp[cursor2]).compareTo(a[cursor1]) < 0) {
2.777 + a[dest--] = a[cursor1--];
2.778 + count1++;
2.779 + count2 = 0;
2.780 + if (--len1 == 0)
2.781 + break outer;
2.782 + } else {
2.783 + a[dest--] = tmp[cursor2--];
2.784 + count2++;
2.785 + count1 = 0;
2.786 + if (--len2 == 1)
2.787 + break outer;
2.788 + }
2.789 + } while ((count1 | count2) < minGallop);
2.790 +
2.791 + /*
2.792 + * One run is winning so consistently that galloping may be a
2.793 + * huge win. So try that, and continue galloping until (if ever)
2.794 + * neither run appears to be winning consistently anymore.
2.795 + */
2.796 + do {
2.797 + assert len1 > 0 && len2 > 1;
2.798 + count1 = len1 - gallopRight((Comparable) tmp[cursor2], a, base1, len1, len1 - 1);
2.799 + if (count1 != 0) {
2.800 + dest -= count1;
2.801 + cursor1 -= count1;
2.802 + len1 -= count1;
2.803 + System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
2.804 + if (len1 == 0)
2.805 + break outer;
2.806 + }
2.807 + a[dest--] = tmp[cursor2--];
2.808 + if (--len2 == 1)
2.809 + break outer;
2.810 +
2.811 + count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, 0, len2, len2 - 1);
2.812 + if (count2 != 0) {
2.813 + dest -= count2;
2.814 + cursor2 -= count2;
2.815 + len2 -= count2;
2.816 + System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
2.817 + if (len2 <= 1)
2.818 + break outer; // len2 == 1 || len2 == 0
2.819 + }
2.820 + a[dest--] = a[cursor1--];
2.821 + if (--len1 == 0)
2.822 + break outer;
2.823 + minGallop--;
2.824 + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
2.825 + if (minGallop < 0)
2.826 + minGallop = 0;
2.827 + minGallop += 2; // Penalize for leaving gallop mode
2.828 + } // End of "outer" loop
2.829 + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
2.830 +
2.831 + if (len2 == 1) {
2.832 + assert len1 > 0;
2.833 + dest -= len1;
2.834 + cursor1 -= len1;
2.835 + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
2.836 + a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
2.837 + } else if (len2 == 0) {
2.838 + throw new IllegalArgumentException(
2.839 + "Comparison method violates its general contract!");
2.840 + } else {
2.841 + assert len1 == 0;
2.842 + assert len2 > 0;
2.843 + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
2.844 + }
2.845 + }
2.846 +
2.847 + /**
2.848 + * Ensures that the external array tmp has at least the specified
2.849 + * number of elements, increasing its size if necessary. The size
2.850 + * increases exponentially to ensure amortized linear time complexity.
2.851 + *
2.852 + * @param minCapacity the minimum required capacity of the tmp array
2.853 + * @return tmp, whether or not it grew
2.854 + */
2.855 + private Object[] ensureCapacity(int minCapacity) {
2.856 + if (tmp.length < minCapacity) {
2.857 + // Compute smallest power of 2 > minCapacity
2.858 + int newSize = minCapacity;
2.859 + newSize |= newSize >> 1;
2.860 + newSize |= newSize >> 2;
2.861 + newSize |= newSize >> 4;
2.862 + newSize |= newSize >> 8;
2.863 + newSize |= newSize >> 16;
2.864 + newSize++;
2.865 +
2.866 + if (newSize < 0) // Not bloody likely!
2.867 + newSize = minCapacity;
2.868 + else
2.869 + newSize = Math.min(newSize, a.length >>> 1);
2.870 +
2.871 + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
2.872 + Object[] newArray = new Object[newSize];
2.873 + tmp = newArray;
2.874 + }
2.875 + return tmp;
2.876 + }
2.877 +
2.878 + /**
2.879 + * Checks that fromIndex and toIndex are in range, and throws an
2.880 + * appropriate exception if they aren't.
2.881 + *
2.882 + * @param arrayLen the length of the array
2.883 + * @param fromIndex the index of the first element of the range
2.884 + * @param toIndex the index after the last element of the range
2.885 + * @throws IllegalArgumentException if fromIndex > toIndex
2.886 + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
2.887 + * or toIndex > arrayLen
2.888 + */
2.889 + private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
2.890 + if (fromIndex > toIndex)
2.891 + throw new IllegalArgumentException("fromIndex(" + fromIndex +
2.892 + ") > toIndex(" + toIndex+")");
2.893 + if (fromIndex < 0)
2.894 + throw new ArrayIndexOutOfBoundsException(fromIndex);
2.895 + if (toIndex > arrayLen)
2.896 + throw new ArrayIndexOutOfBoundsException(toIndex);
2.897 + }
2.898 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/emul/compact/src/main/java/java/util/DualPivotQuicksort.java Wed Jan 23 23:19:47 2013 +0100
3.3 @@ -0,0 +1,3018 @@
3.4 +/*
3.5 + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3.7 + *
3.8 + * This code is free software; you can redistribute it and/or modify it
3.9 + * under the terms of the GNU General Public License version 2 only, as
3.10 + * published by the Free Software Foundation. Oracle designates this
3.11 + * particular file as subject to the "Classpath" exception as provided
3.12 + * by Oracle in the LICENSE file that accompanied this code.
3.13 + *
3.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
3.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
3.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
3.17 + * version 2 for more details (a copy is included in the LICENSE file that
3.18 + * accompanied this code).
3.19 + *
3.20 + * You should have received a copy of the GNU General Public License version
3.21 + * 2 along with this work; if not, write to the Free Software Foundation,
3.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
3.23 + *
3.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
3.25 + * or visit www.oracle.com if you need additional information or have any
3.26 + * questions.
3.27 + */
3.28 +
3.29 +package java.util;
3.30 +
3.31 +/**
3.32 + * This class implements the Dual-Pivot Quicksort algorithm by
3.33 + * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
3.34 + * offers O(n log(n)) performance on many data sets that cause other
3.35 + * quicksorts to degrade to quadratic performance, and is typically
3.36 + * faster than traditional (one-pivot) Quicksort implementations.
3.37 + *
3.38 + * @author Vladimir Yaroslavskiy
3.39 + * @author Jon Bentley
3.40 + * @author Josh Bloch
3.41 + *
3.42 + * @version 2011.02.11 m765.827.12i:5\7pm
3.43 + * @since 1.7
3.44 + */
3.45 +final class DualPivotQuicksort {
3.46 +
3.47 + /**
3.48 + * Prevents instantiation.
3.49 + */
3.50 + private DualPivotQuicksort() {}
3.51 +
3.52 + /*
3.53 + * Tuning parameters.
3.54 + */
3.55 +
3.56 + /**
3.57 + * The maximum number of runs in merge sort.
3.58 + */
3.59 + private static final int MAX_RUN_COUNT = 67;
3.60 +
3.61 + /**
3.62 + * The maximum length of run in merge sort.
3.63 + */
3.64 + private static final int MAX_RUN_LENGTH = 33;
3.65 +
3.66 + /**
3.67 + * If the length of an array to be sorted is less than this
3.68 + * constant, Quicksort is used in preference to merge sort.
3.69 + */
3.70 + private static final int QUICKSORT_THRESHOLD = 286;
3.71 +
3.72 + /**
3.73 + * If the length of an array to be sorted is less than this
3.74 + * constant, insertion sort is used in preference to Quicksort.
3.75 + */
3.76 + private static final int INSERTION_SORT_THRESHOLD = 47;
3.77 +
3.78 + /**
3.79 + * If the length of a byte array to be sorted is greater than this
3.80 + * constant, counting sort is used in preference to insertion sort.
3.81 + */
3.82 + private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
3.83 +
3.84 + /**
3.85 + * If the length of a short or char array to be sorted is greater
3.86 + * than this constant, counting sort is used in preference to Quicksort.
3.87 + */
3.88 + private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
3.89 +
3.90 + /*
3.91 + * Sorting methods for seven primitive types.
3.92 + */
3.93 +
3.94 + /**
3.95 + * Sorts the specified array.
3.96 + *
3.97 + * @param a the array to be sorted
3.98 + */
3.99 + public static void sort(int[] a) {
3.100 + sort(a, 0, a.length - 1);
3.101 + }
3.102 +
3.103 + /**
3.104 + * Sorts the specified range of the array.
3.105 + *
3.106 + * @param a the array to be sorted
3.107 + * @param left the index of the first element, inclusive, to be sorted
3.108 + * @param right the index of the last element, inclusive, to be sorted
3.109 + */
3.110 + public static void sort(int[] a, int left, int right) {
3.111 + // Use Quicksort on small arrays
3.112 + if (right - left < QUICKSORT_THRESHOLD) {
3.113 + sort(a, left, right, true);
3.114 + return;
3.115 + }
3.116 +
3.117 + /*
3.118 + * Index run[i] is the start of i-th run
3.119 + * (ascending or descending sequence).
3.120 + */
3.121 + int[] run = new int[MAX_RUN_COUNT + 1];
3.122 + int count = 0; run[0] = left;
3.123 +
3.124 + // Check if the array is nearly sorted
3.125 + for (int k = left; k < right; run[count] = k) {
3.126 + if (a[k] < a[k + 1]) { // ascending
3.127 + while (++k <= right && a[k - 1] <= a[k]);
3.128 + } else if (a[k] > a[k + 1]) { // descending
3.129 + while (++k <= right && a[k - 1] >= a[k]);
3.130 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.131 + int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.132 + }
3.133 + } else { // equal
3.134 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.135 + if (--m == 0) {
3.136 + sort(a, left, right, true);
3.137 + return;
3.138 + }
3.139 + }
3.140 + }
3.141 +
3.142 + /*
3.143 + * The array is not highly structured,
3.144 + * use Quicksort instead of merge sort.
3.145 + */
3.146 + if (++count == MAX_RUN_COUNT) {
3.147 + sort(a, left, right, true);
3.148 + return;
3.149 + }
3.150 + }
3.151 +
3.152 + // Check special cases
3.153 + if (run[count] == right++) { // The last run contains one element
3.154 + run[++count] = right;
3.155 + } else if (count == 1) { // The array is already sorted
3.156 + return;
3.157 + }
3.158 +
3.159 + /*
3.160 + * Create temporary array, which is used for merging.
3.161 + * Implementation note: variable "right" is increased by 1.
3.162 + */
3.163 + int[] b; byte odd = 0;
3.164 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.165 +
3.166 + if (odd == 0) {
3.167 + b = a; a = new int[b.length];
3.168 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.169 + } else {
3.170 + b = new int[a.length];
3.171 + }
3.172 +
3.173 + // Merging
3.174 + for (int last; count > 1; count = last) {
3.175 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.176 + int hi = run[k], mi = run[k - 1];
3.177 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.178 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.179 + b[i] = a[p++];
3.180 + } else {
3.181 + b[i] = a[q++];
3.182 + }
3.183 + }
3.184 + run[++last] = hi;
3.185 + }
3.186 + if ((count & 1) != 0) {
3.187 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.188 + b[i] = a[i]
3.189 + );
3.190 + run[++last] = right;
3.191 + }
3.192 + int[] t = a; a = b; b = t;
3.193 + }
3.194 + }
3.195 +
3.196 + /**
3.197 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.198 + *
3.199 + * @param a the array to be sorted
3.200 + * @param left the index of the first element, inclusive, to be sorted
3.201 + * @param right the index of the last element, inclusive, to be sorted
3.202 + * @param leftmost indicates if this part is the leftmost in the range
3.203 + */
3.204 + private static void sort(int[] a, int left, int right, boolean leftmost) {
3.205 + int length = right - left + 1;
3.206 +
3.207 + // Use insertion sort on tiny arrays
3.208 + if (length < INSERTION_SORT_THRESHOLD) {
3.209 + if (leftmost) {
3.210 + /*
3.211 + * Traditional (without sentinel) insertion sort,
3.212 + * optimized for server VM, is used in case of
3.213 + * the leftmost part.
3.214 + */
3.215 + for (int i = left, j = i; i < right; j = ++i) {
3.216 + int ai = a[i + 1];
3.217 + while (ai < a[j]) {
3.218 + a[j + 1] = a[j];
3.219 + if (j-- == left) {
3.220 + break;
3.221 + }
3.222 + }
3.223 + a[j + 1] = ai;
3.224 + }
3.225 + } else {
3.226 + /*
3.227 + * Skip the longest ascending sequence.
3.228 + */
3.229 + do {
3.230 + if (left >= right) {
3.231 + return;
3.232 + }
3.233 + } while (a[++left] >= a[left - 1]);
3.234 +
3.235 + /*
3.236 + * Every element from adjoining part plays the role
3.237 + * of sentinel, therefore this allows us to avoid the
3.238 + * left range check on each iteration. Moreover, we use
3.239 + * the more optimized algorithm, so called pair insertion
3.240 + * sort, which is faster (in the context of Quicksort)
3.241 + * than traditional implementation of insertion sort.
3.242 + */
3.243 + for (int k = left; ++left <= right; k = ++left) {
3.244 + int a1 = a[k], a2 = a[left];
3.245 +
3.246 + if (a1 < a2) {
3.247 + a2 = a1; a1 = a[left];
3.248 + }
3.249 + while (a1 < a[--k]) {
3.250 + a[k + 2] = a[k];
3.251 + }
3.252 + a[++k + 1] = a1;
3.253 +
3.254 + while (a2 < a[--k]) {
3.255 + a[k + 1] = a[k];
3.256 + }
3.257 + a[k + 1] = a2;
3.258 + }
3.259 + int last = a[right];
3.260 +
3.261 + while (last < a[--right]) {
3.262 + a[right + 1] = a[right];
3.263 + }
3.264 + a[right + 1] = last;
3.265 + }
3.266 + return;
3.267 + }
3.268 +
3.269 + // Inexpensive approximation of length / 7
3.270 + int seventh = (length >> 3) + (length >> 6) + 1;
3.271 +
3.272 + /*
3.273 + * Sort five evenly spaced elements around (and including) the
3.274 + * center element in the range. These elements will be used for
3.275 + * pivot selection as described below. The choice for spacing
3.276 + * these elements was empirically determined to work well on
3.277 + * a wide variety of inputs.
3.278 + */
3.279 + int e3 = (left + right) >>> 1; // The midpoint
3.280 + int e2 = e3 - seventh;
3.281 + int e1 = e2 - seventh;
3.282 + int e4 = e3 + seventh;
3.283 + int e5 = e4 + seventh;
3.284 +
3.285 + // Sort these elements using insertion sort
3.286 + if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.287 +
3.288 + if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.289 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.290 + }
3.291 + if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.292 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.293 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.294 + }
3.295 + }
3.296 + if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.297 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.298 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.299 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.300 + }
3.301 + }
3.302 + }
3.303 +
3.304 + // Pointers
3.305 + int less = left; // The index of the first element of center part
3.306 + int great = right; // The index before the first element of right part
3.307 +
3.308 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.309 + /*
3.310 + * Use the second and fourth of the five sorted elements as pivots.
3.311 + * These values are inexpensive approximations of the first and
3.312 + * second terciles of the array. Note that pivot1 <= pivot2.
3.313 + */
3.314 + int pivot1 = a[e2];
3.315 + int pivot2 = a[e4];
3.316 +
3.317 + /*
3.318 + * The first and the last elements to be sorted are moved to the
3.319 + * locations formerly occupied by the pivots. When partitioning
3.320 + * is complete, the pivots are swapped back into their final
3.321 + * positions, and excluded from subsequent sorting.
3.322 + */
3.323 + a[e2] = a[left];
3.324 + a[e4] = a[right];
3.325 +
3.326 + /*
3.327 + * Skip elements, which are less or greater than pivot values.
3.328 + */
3.329 + while (a[++less] < pivot1);
3.330 + while (a[--great] > pivot2);
3.331 +
3.332 + /*
3.333 + * Partitioning:
3.334 + *
3.335 + * left part center part right part
3.336 + * +--------------------------------------------------------------+
3.337 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.338 + * +--------------------------------------------------------------+
3.339 + * ^ ^ ^
3.340 + * | | |
3.341 + * less k great
3.342 + *
3.343 + * Invariants:
3.344 + *
3.345 + * all in (left, less) < pivot1
3.346 + * pivot1 <= all in [less, k) <= pivot2
3.347 + * all in (great, right) > pivot2
3.348 + *
3.349 + * Pointer k is the first index of ?-part.
3.350 + */
3.351 + outer:
3.352 + for (int k = less - 1; ++k <= great; ) {
3.353 + int ak = a[k];
3.354 + if (ak < pivot1) { // Move a[k] to left part
3.355 + a[k] = a[less];
3.356 + /*
3.357 + * Here and below we use "a[i] = b; i++;" instead
3.358 + * of "a[i++] = b;" due to performance issue.
3.359 + */
3.360 + a[less] = ak;
3.361 + ++less;
3.362 + } else if (ak > pivot2) { // Move a[k] to right part
3.363 + while (a[great] > pivot2) {
3.364 + if (great-- == k) {
3.365 + break outer;
3.366 + }
3.367 + }
3.368 + if (a[great] < pivot1) { // a[great] <= pivot2
3.369 + a[k] = a[less];
3.370 + a[less] = a[great];
3.371 + ++less;
3.372 + } else { // pivot1 <= a[great] <= pivot2
3.373 + a[k] = a[great];
3.374 + }
3.375 + /*
3.376 + * Here and below we use "a[i] = b; i--;" instead
3.377 + * of "a[i--] = b;" due to performance issue.
3.378 + */
3.379 + a[great] = ak;
3.380 + --great;
3.381 + }
3.382 + }
3.383 +
3.384 + // Swap pivots into their final positions
3.385 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.386 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.387 +
3.388 + // Sort left and right parts recursively, excluding known pivots
3.389 + sort(a, left, less - 2, leftmost);
3.390 + sort(a, great + 2, right, false);
3.391 +
3.392 + /*
3.393 + * If center part is too large (comprises > 4/7 of the array),
3.394 + * swap internal pivot values to ends.
3.395 + */
3.396 + if (less < e1 && e5 < great) {
3.397 + /*
3.398 + * Skip elements, which are equal to pivot values.
3.399 + */
3.400 + while (a[less] == pivot1) {
3.401 + ++less;
3.402 + }
3.403 +
3.404 + while (a[great] == pivot2) {
3.405 + --great;
3.406 + }
3.407 +
3.408 + /*
3.409 + * Partitioning:
3.410 + *
3.411 + * left part center part right part
3.412 + * +----------------------------------------------------------+
3.413 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.414 + * +----------------------------------------------------------+
3.415 + * ^ ^ ^
3.416 + * | | |
3.417 + * less k great
3.418 + *
3.419 + * Invariants:
3.420 + *
3.421 + * all in (*, less) == pivot1
3.422 + * pivot1 < all in [less, k) < pivot2
3.423 + * all in (great, *) == pivot2
3.424 + *
3.425 + * Pointer k is the first index of ?-part.
3.426 + */
3.427 + outer:
3.428 + for (int k = less - 1; ++k <= great; ) {
3.429 + int ak = a[k];
3.430 + if (ak == pivot1) { // Move a[k] to left part
3.431 + a[k] = a[less];
3.432 + a[less] = ak;
3.433 + ++less;
3.434 + } else if (ak == pivot2) { // Move a[k] to right part
3.435 + while (a[great] == pivot2) {
3.436 + if (great-- == k) {
3.437 + break outer;
3.438 + }
3.439 + }
3.440 + if (a[great] == pivot1) { // a[great] < pivot2
3.441 + a[k] = a[less];
3.442 + /*
3.443 + * Even though a[great] equals to pivot1, the
3.444 + * assignment a[less] = pivot1 may be incorrect,
3.445 + * if a[great] and pivot1 are floating-point zeros
3.446 + * of different signs. Therefore in float and
3.447 + * double sorting methods we have to use more
3.448 + * accurate assignment a[less] = a[great].
3.449 + */
3.450 + a[less] = pivot1;
3.451 + ++less;
3.452 + } else { // pivot1 < a[great] < pivot2
3.453 + a[k] = a[great];
3.454 + }
3.455 + a[great] = ak;
3.456 + --great;
3.457 + }
3.458 + }
3.459 + }
3.460 +
3.461 + // Sort center part recursively
3.462 + sort(a, less, great, false);
3.463 +
3.464 + } else { // Partitioning with one pivot
3.465 + /*
3.466 + * Use the third of the five sorted elements as pivot.
3.467 + * This value is inexpensive approximation of the median.
3.468 + */
3.469 + int pivot = a[e3];
3.470 +
3.471 + /*
3.472 + * Partitioning degenerates to the traditional 3-way
3.473 + * (or "Dutch National Flag") schema:
3.474 + *
3.475 + * left part center part right part
3.476 + * +-------------------------------------------------+
3.477 + * | < pivot | == pivot | ? | > pivot |
3.478 + * +-------------------------------------------------+
3.479 + * ^ ^ ^
3.480 + * | | |
3.481 + * less k great
3.482 + *
3.483 + * Invariants:
3.484 + *
3.485 + * all in (left, less) < pivot
3.486 + * all in [less, k) == pivot
3.487 + * all in (great, right) > pivot
3.488 + *
3.489 + * Pointer k is the first index of ?-part.
3.490 + */
3.491 + for (int k = less; k <= great; ++k) {
3.492 + if (a[k] == pivot) {
3.493 + continue;
3.494 + }
3.495 + int ak = a[k];
3.496 + if (ak < pivot) { // Move a[k] to left part
3.497 + a[k] = a[less];
3.498 + a[less] = ak;
3.499 + ++less;
3.500 + } else { // a[k] > pivot - Move a[k] to right part
3.501 + while (a[great] > pivot) {
3.502 + --great;
3.503 + }
3.504 + if (a[great] < pivot) { // a[great] <= pivot
3.505 + a[k] = a[less];
3.506 + a[less] = a[great];
3.507 + ++less;
3.508 + } else { // a[great] == pivot
3.509 + /*
3.510 + * Even though a[great] equals to pivot, the
3.511 + * assignment a[k] = pivot may be incorrect,
3.512 + * if a[great] and pivot are floating-point
3.513 + * zeros of different signs. Therefore in float
3.514 + * and double sorting methods we have to use
3.515 + * more accurate assignment a[k] = a[great].
3.516 + */
3.517 + a[k] = pivot;
3.518 + }
3.519 + a[great] = ak;
3.520 + --great;
3.521 + }
3.522 + }
3.523 +
3.524 + /*
3.525 + * Sort left and right parts recursively.
3.526 + * All elements from center part are equal
3.527 + * and, therefore, already sorted.
3.528 + */
3.529 + sort(a, left, less - 1, leftmost);
3.530 + sort(a, great + 1, right, false);
3.531 + }
3.532 + }
3.533 +
3.534 + /**
3.535 + * Sorts the specified array.
3.536 + *
3.537 + * @param a the array to be sorted
3.538 + */
3.539 + public static void sort(long[] a) {
3.540 + sort(a, 0, a.length - 1);
3.541 + }
3.542 +
3.543 + /**
3.544 + * Sorts the specified range of the array.
3.545 + *
3.546 + * @param a the array to be sorted
3.547 + * @param left the index of the first element, inclusive, to be sorted
3.548 + * @param right the index of the last element, inclusive, to be sorted
3.549 + */
3.550 + public static void sort(long[] a, int left, int right) {
3.551 + // Use Quicksort on small arrays
3.552 + if (right - left < QUICKSORT_THRESHOLD) {
3.553 + sort(a, left, right, true);
3.554 + return;
3.555 + }
3.556 +
3.557 + /*
3.558 + * Index run[i] is the start of i-th run
3.559 + * (ascending or descending sequence).
3.560 + */
3.561 + int[] run = new int[MAX_RUN_COUNT + 1];
3.562 + int count = 0; run[0] = left;
3.563 +
3.564 + // Check if the array is nearly sorted
3.565 + for (int k = left; k < right; run[count] = k) {
3.566 + if (a[k] < a[k + 1]) { // ascending
3.567 + while (++k <= right && a[k - 1] <= a[k]);
3.568 + } else if (a[k] > a[k + 1]) { // descending
3.569 + while (++k <= right && a[k - 1] >= a[k]);
3.570 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.571 + long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.572 + }
3.573 + } else { // equal
3.574 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.575 + if (--m == 0) {
3.576 + sort(a, left, right, true);
3.577 + return;
3.578 + }
3.579 + }
3.580 + }
3.581 +
3.582 + /*
3.583 + * The array is not highly structured,
3.584 + * use Quicksort instead of merge sort.
3.585 + */
3.586 + if (++count == MAX_RUN_COUNT) {
3.587 + sort(a, left, right, true);
3.588 + return;
3.589 + }
3.590 + }
3.591 +
3.592 + // Check special cases
3.593 + if (run[count] == right++) { // The last run contains one element
3.594 + run[++count] = right;
3.595 + } else if (count == 1) { // The array is already sorted
3.596 + return;
3.597 + }
3.598 +
3.599 + /*
3.600 + * Create temporary array, which is used for merging.
3.601 + * Implementation note: variable "right" is increased by 1.
3.602 + */
3.603 + long[] b; byte odd = 0;
3.604 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.605 +
3.606 + if (odd == 0) {
3.607 + b = a; a = new long[b.length];
3.608 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.609 + } else {
3.610 + b = new long[a.length];
3.611 + }
3.612 +
3.613 + // Merging
3.614 + for (int last; count > 1; count = last) {
3.615 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.616 + int hi = run[k], mi = run[k - 1];
3.617 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.618 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.619 + b[i] = a[p++];
3.620 + } else {
3.621 + b[i] = a[q++];
3.622 + }
3.623 + }
3.624 + run[++last] = hi;
3.625 + }
3.626 + if ((count & 1) != 0) {
3.627 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.628 + b[i] = a[i]
3.629 + );
3.630 + run[++last] = right;
3.631 + }
3.632 + long[] t = a; a = b; b = t;
3.633 + }
3.634 + }
3.635 +
3.636 + /**
3.637 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.638 + *
3.639 + * @param a the array to be sorted
3.640 + * @param left the index of the first element, inclusive, to be sorted
3.641 + * @param right the index of the last element, inclusive, to be sorted
3.642 + * @param leftmost indicates if this part is the leftmost in the range
3.643 + */
3.644 + private static void sort(long[] a, int left, int right, boolean leftmost) {
3.645 + int length = right - left + 1;
3.646 +
3.647 + // Use insertion sort on tiny arrays
3.648 + if (length < INSERTION_SORT_THRESHOLD) {
3.649 + if (leftmost) {
3.650 + /*
3.651 + * Traditional (without sentinel) insertion sort,
3.652 + * optimized for server VM, is used in case of
3.653 + * the leftmost part.
3.654 + */
3.655 + for (int i = left, j = i; i < right; j = ++i) {
3.656 + long ai = a[i + 1];
3.657 + while (ai < a[j]) {
3.658 + a[j + 1] = a[j];
3.659 + if (j-- == left) {
3.660 + break;
3.661 + }
3.662 + }
3.663 + a[j + 1] = ai;
3.664 + }
3.665 + } else {
3.666 + /*
3.667 + * Skip the longest ascending sequence.
3.668 + */
3.669 + do {
3.670 + if (left >= right) {
3.671 + return;
3.672 + }
3.673 + } while (a[++left] >= a[left - 1]);
3.674 +
3.675 + /*
3.676 + * Every element from adjoining part plays the role
3.677 + * of sentinel, therefore this allows us to avoid the
3.678 + * left range check on each iteration. Moreover, we use
3.679 + * the more optimized algorithm, so called pair insertion
3.680 + * sort, which is faster (in the context of Quicksort)
3.681 + * than traditional implementation of insertion sort.
3.682 + */
3.683 + for (int k = left; ++left <= right; k = ++left) {
3.684 + long a1 = a[k], a2 = a[left];
3.685 +
3.686 + if (a1 < a2) {
3.687 + a2 = a1; a1 = a[left];
3.688 + }
3.689 + while (a1 < a[--k]) {
3.690 + a[k + 2] = a[k];
3.691 + }
3.692 + a[++k + 1] = a1;
3.693 +
3.694 + while (a2 < a[--k]) {
3.695 + a[k + 1] = a[k];
3.696 + }
3.697 + a[k + 1] = a2;
3.698 + }
3.699 + long last = a[right];
3.700 +
3.701 + while (last < a[--right]) {
3.702 + a[right + 1] = a[right];
3.703 + }
3.704 + a[right + 1] = last;
3.705 + }
3.706 + return;
3.707 + }
3.708 +
3.709 + // Inexpensive approximation of length / 7
3.710 + int seventh = (length >> 3) + (length >> 6) + 1;
3.711 +
3.712 + /*
3.713 + * Sort five evenly spaced elements around (and including) the
3.714 + * center element in the range. These elements will be used for
3.715 + * pivot selection as described below. The choice for spacing
3.716 + * these elements was empirically determined to work well on
3.717 + * a wide variety of inputs.
3.718 + */
3.719 + int e3 = (left + right) >>> 1; // The midpoint
3.720 + int e2 = e3 - seventh;
3.721 + int e1 = e2 - seventh;
3.722 + int e4 = e3 + seventh;
3.723 + int e5 = e4 + seventh;
3.724 +
3.725 + // Sort these elements using insertion sort
3.726 + if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.727 +
3.728 + if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.729 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.730 + }
3.731 + if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.732 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.733 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.734 + }
3.735 + }
3.736 + if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.737 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.738 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.739 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.740 + }
3.741 + }
3.742 + }
3.743 +
3.744 + // Pointers
3.745 + int less = left; // The index of the first element of center part
3.746 + int great = right; // The index before the first element of right part
3.747 +
3.748 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.749 + /*
3.750 + * Use the second and fourth of the five sorted elements as pivots.
3.751 + * These values are inexpensive approximations of the first and
3.752 + * second terciles of the array. Note that pivot1 <= pivot2.
3.753 + */
3.754 + long pivot1 = a[e2];
3.755 + long pivot2 = a[e4];
3.756 +
3.757 + /*
3.758 + * The first and the last elements to be sorted are moved to the
3.759 + * locations formerly occupied by the pivots. When partitioning
3.760 + * is complete, the pivots are swapped back into their final
3.761 + * positions, and excluded from subsequent sorting.
3.762 + */
3.763 + a[e2] = a[left];
3.764 + a[e4] = a[right];
3.765 +
3.766 + /*
3.767 + * Skip elements, which are less or greater than pivot values.
3.768 + */
3.769 + while (a[++less] < pivot1);
3.770 + while (a[--great] > pivot2);
3.771 +
3.772 + /*
3.773 + * Partitioning:
3.774 + *
3.775 + * left part center part right part
3.776 + * +--------------------------------------------------------------+
3.777 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.778 + * +--------------------------------------------------------------+
3.779 + * ^ ^ ^
3.780 + * | | |
3.781 + * less k great
3.782 + *
3.783 + * Invariants:
3.784 + *
3.785 + * all in (left, less) < pivot1
3.786 + * pivot1 <= all in [less, k) <= pivot2
3.787 + * all in (great, right) > pivot2
3.788 + *
3.789 + * Pointer k is the first index of ?-part.
3.790 + */
3.791 + outer:
3.792 + for (int k = less - 1; ++k <= great; ) {
3.793 + long ak = a[k];
3.794 + if (ak < pivot1) { // Move a[k] to left part
3.795 + a[k] = a[less];
3.796 + /*
3.797 + * Here and below we use "a[i] = b; i++;" instead
3.798 + * of "a[i++] = b;" due to performance issue.
3.799 + */
3.800 + a[less] = ak;
3.801 + ++less;
3.802 + } else if (ak > pivot2) { // Move a[k] to right part
3.803 + while (a[great] > pivot2) {
3.804 + if (great-- == k) {
3.805 + break outer;
3.806 + }
3.807 + }
3.808 + if (a[great] < pivot1) { // a[great] <= pivot2
3.809 + a[k] = a[less];
3.810 + a[less] = a[great];
3.811 + ++less;
3.812 + } else { // pivot1 <= a[great] <= pivot2
3.813 + a[k] = a[great];
3.814 + }
3.815 + /*
3.816 + * Here and below we use "a[i] = b; i--;" instead
3.817 + * of "a[i--] = b;" due to performance issue.
3.818 + */
3.819 + a[great] = ak;
3.820 + --great;
3.821 + }
3.822 + }
3.823 +
3.824 + // Swap pivots into their final positions
3.825 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.826 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.827 +
3.828 + // Sort left and right parts recursively, excluding known pivots
3.829 + sort(a, left, less - 2, leftmost);
3.830 + sort(a, great + 2, right, false);
3.831 +
3.832 + /*
3.833 + * If center part is too large (comprises > 4/7 of the array),
3.834 + * swap internal pivot values to ends.
3.835 + */
3.836 + if (less < e1 && e5 < great) {
3.837 + /*
3.838 + * Skip elements, which are equal to pivot values.
3.839 + */
3.840 + while (a[less] == pivot1) {
3.841 + ++less;
3.842 + }
3.843 +
3.844 + while (a[great] == pivot2) {
3.845 + --great;
3.846 + }
3.847 +
3.848 + /*
3.849 + * Partitioning:
3.850 + *
3.851 + * left part center part right part
3.852 + * +----------------------------------------------------------+
3.853 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.854 + * +----------------------------------------------------------+
3.855 + * ^ ^ ^
3.856 + * | | |
3.857 + * less k great
3.858 + *
3.859 + * Invariants:
3.860 + *
3.861 + * all in (*, less) == pivot1
3.862 + * pivot1 < all in [less, k) < pivot2
3.863 + * all in (great, *) == pivot2
3.864 + *
3.865 + * Pointer k is the first index of ?-part.
3.866 + */
3.867 + outer:
3.868 + for (int k = less - 1; ++k <= great; ) {
3.869 + long ak = a[k];
3.870 + if (ak == pivot1) { // Move a[k] to left part
3.871 + a[k] = a[less];
3.872 + a[less] = ak;
3.873 + ++less;
3.874 + } else if (ak == pivot2) { // Move a[k] to right part
3.875 + while (a[great] == pivot2) {
3.876 + if (great-- == k) {
3.877 + break outer;
3.878 + }
3.879 + }
3.880 + if (a[great] == pivot1) { // a[great] < pivot2
3.881 + a[k] = a[less];
3.882 + /*
3.883 + * Even though a[great] equals to pivot1, the
3.884 + * assignment a[less] = pivot1 may be incorrect,
3.885 + * if a[great] and pivot1 are floating-point zeros
3.886 + * of different signs. Therefore in float and
3.887 + * double sorting methods we have to use more
3.888 + * accurate assignment a[less] = a[great].
3.889 + */
3.890 + a[less] = pivot1;
3.891 + ++less;
3.892 + } else { // pivot1 < a[great] < pivot2
3.893 + a[k] = a[great];
3.894 + }
3.895 + a[great] = ak;
3.896 + --great;
3.897 + }
3.898 + }
3.899 + }
3.900 +
3.901 + // Sort center part recursively
3.902 + sort(a, less, great, false);
3.903 +
3.904 + } else { // Partitioning with one pivot
3.905 + /*
3.906 + * Use the third of the five sorted elements as pivot.
3.907 + * This value is inexpensive approximation of the median.
3.908 + */
3.909 + long pivot = a[e3];
3.910 +
3.911 + /*
3.912 + * Partitioning degenerates to the traditional 3-way
3.913 + * (or "Dutch National Flag") schema:
3.914 + *
3.915 + * left part center part right part
3.916 + * +-------------------------------------------------+
3.917 + * | < pivot | == pivot | ? | > pivot |
3.918 + * +-------------------------------------------------+
3.919 + * ^ ^ ^
3.920 + * | | |
3.921 + * less k great
3.922 + *
3.923 + * Invariants:
3.924 + *
3.925 + * all in (left, less) < pivot
3.926 + * all in [less, k) == pivot
3.927 + * all in (great, right) > pivot
3.928 + *
3.929 + * Pointer k is the first index of ?-part.
3.930 + */
3.931 + for (int k = less; k <= great; ++k) {
3.932 + if (a[k] == pivot) {
3.933 + continue;
3.934 + }
3.935 + long ak = a[k];
3.936 + if (ak < pivot) { // Move a[k] to left part
3.937 + a[k] = a[less];
3.938 + a[less] = ak;
3.939 + ++less;
3.940 + } else { // a[k] > pivot - Move a[k] to right part
3.941 + while (a[great] > pivot) {
3.942 + --great;
3.943 + }
3.944 + if (a[great] < pivot) { // a[great] <= pivot
3.945 + a[k] = a[less];
3.946 + a[less] = a[great];
3.947 + ++less;
3.948 + } else { // a[great] == pivot
3.949 + /*
3.950 + * Even though a[great] equals to pivot, the
3.951 + * assignment a[k] = pivot may be incorrect,
3.952 + * if a[great] and pivot are floating-point
3.953 + * zeros of different signs. Therefore in float
3.954 + * and double sorting methods we have to use
3.955 + * more accurate assignment a[k] = a[great].
3.956 + */
3.957 + a[k] = pivot;
3.958 + }
3.959 + a[great] = ak;
3.960 + --great;
3.961 + }
3.962 + }
3.963 +
3.964 + /*
3.965 + * Sort left and right parts recursively.
3.966 + * All elements from center part are equal
3.967 + * and, therefore, already sorted.
3.968 + */
3.969 + sort(a, left, less - 1, leftmost);
3.970 + sort(a, great + 1, right, false);
3.971 + }
3.972 + }
3.973 +
3.974 + /**
3.975 + * Sorts the specified array.
3.976 + *
3.977 + * @param a the array to be sorted
3.978 + */
3.979 + public static void sort(short[] a) {
3.980 + sort(a, 0, a.length - 1);
3.981 + }
3.982 +
3.983 + /**
3.984 + * Sorts the specified range of the array.
3.985 + *
3.986 + * @param a the array to be sorted
3.987 + * @param left the index of the first element, inclusive, to be sorted
3.988 + * @param right the index of the last element, inclusive, to be sorted
3.989 + */
3.990 + public static void sort(short[] a, int left, int right) {
3.991 + // Use counting sort on large arrays
3.992 + if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
3.993 + int[] count = new int[NUM_SHORT_VALUES];
3.994 +
3.995 + for (int i = left - 1; ++i <= right;
3.996 + count[a[i] - Short.MIN_VALUE]++
3.997 + );
3.998 + for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
3.999 + while (count[--i] == 0);
3.1000 + short value = (short) (i + Short.MIN_VALUE);
3.1001 + int s = count[i];
3.1002 +
3.1003 + do {
3.1004 + a[--k] = value;
3.1005 + } while (--s > 0);
3.1006 + }
3.1007 + } else { // Use Dual-Pivot Quicksort on small arrays
3.1008 + doSort(a, left, right);
3.1009 + }
3.1010 + }
3.1011 +
3.1012 + /** The number of distinct short values. */
3.1013 + private static final int NUM_SHORT_VALUES = 1 << 16;
3.1014 +
3.1015 + /**
3.1016 + * Sorts the specified range of the array.
3.1017 + *
3.1018 + * @param a the array to be sorted
3.1019 + * @param left the index of the first element, inclusive, to be sorted
3.1020 + * @param right the index of the last element, inclusive, to be sorted
3.1021 + */
3.1022 + private static void doSort(short[] a, int left, int right) {
3.1023 + // Use Quicksort on small arrays
3.1024 + if (right - left < QUICKSORT_THRESHOLD) {
3.1025 + sort(a, left, right, true);
3.1026 + return;
3.1027 + }
3.1028 +
3.1029 + /*
3.1030 + * Index run[i] is the start of i-th run
3.1031 + * (ascending or descending sequence).
3.1032 + */
3.1033 + int[] run = new int[MAX_RUN_COUNT + 1];
3.1034 + int count = 0; run[0] = left;
3.1035 +
3.1036 + // Check if the array is nearly sorted
3.1037 + for (int k = left; k < right; run[count] = k) {
3.1038 + if (a[k] < a[k + 1]) { // ascending
3.1039 + while (++k <= right && a[k - 1] <= a[k]);
3.1040 + } else if (a[k] > a[k + 1]) { // descending
3.1041 + while (++k <= right && a[k - 1] >= a[k]);
3.1042 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.1043 + short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.1044 + }
3.1045 + } else { // equal
3.1046 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.1047 + if (--m == 0) {
3.1048 + sort(a, left, right, true);
3.1049 + return;
3.1050 + }
3.1051 + }
3.1052 + }
3.1053 +
3.1054 + /*
3.1055 + * The array is not highly structured,
3.1056 + * use Quicksort instead of merge sort.
3.1057 + */
3.1058 + if (++count == MAX_RUN_COUNT) {
3.1059 + sort(a, left, right, true);
3.1060 + return;
3.1061 + }
3.1062 + }
3.1063 +
3.1064 + // Check special cases
3.1065 + if (run[count] == right++) { // The last run contains one element
3.1066 + run[++count] = right;
3.1067 + } else if (count == 1) { // The array is already sorted
3.1068 + return;
3.1069 + }
3.1070 +
3.1071 + /*
3.1072 + * Create temporary array, which is used for merging.
3.1073 + * Implementation note: variable "right" is increased by 1.
3.1074 + */
3.1075 + short[] b; byte odd = 0;
3.1076 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.1077 +
3.1078 + if (odd == 0) {
3.1079 + b = a; a = new short[b.length];
3.1080 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.1081 + } else {
3.1082 + b = new short[a.length];
3.1083 + }
3.1084 +
3.1085 + // Merging
3.1086 + for (int last; count > 1; count = last) {
3.1087 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.1088 + int hi = run[k], mi = run[k - 1];
3.1089 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.1090 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.1091 + b[i] = a[p++];
3.1092 + } else {
3.1093 + b[i] = a[q++];
3.1094 + }
3.1095 + }
3.1096 + run[++last] = hi;
3.1097 + }
3.1098 + if ((count & 1) != 0) {
3.1099 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.1100 + b[i] = a[i]
3.1101 + );
3.1102 + run[++last] = right;
3.1103 + }
3.1104 + short[] t = a; a = b; b = t;
3.1105 + }
3.1106 + }
3.1107 +
3.1108 + /**
3.1109 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.1110 + *
3.1111 + * @param a the array to be sorted
3.1112 + * @param left the index of the first element, inclusive, to be sorted
3.1113 + * @param right the index of the last element, inclusive, to be sorted
3.1114 + * @param leftmost indicates if this part is the leftmost in the range
3.1115 + */
3.1116 + private static void sort(short[] a, int left, int right, boolean leftmost) {
3.1117 + int length = right - left + 1;
3.1118 +
3.1119 + // Use insertion sort on tiny arrays
3.1120 + if (length < INSERTION_SORT_THRESHOLD) {
3.1121 + if (leftmost) {
3.1122 + /*
3.1123 + * Traditional (without sentinel) insertion sort,
3.1124 + * optimized for server VM, is used in case of
3.1125 + * the leftmost part.
3.1126 + */
3.1127 + for (int i = left, j = i; i < right; j = ++i) {
3.1128 + short ai = a[i + 1];
3.1129 + while (ai < a[j]) {
3.1130 + a[j + 1] = a[j];
3.1131 + if (j-- == left) {
3.1132 + break;
3.1133 + }
3.1134 + }
3.1135 + a[j + 1] = ai;
3.1136 + }
3.1137 + } else {
3.1138 + /*
3.1139 + * Skip the longest ascending sequence.
3.1140 + */
3.1141 + do {
3.1142 + if (left >= right) {
3.1143 + return;
3.1144 + }
3.1145 + } while (a[++left] >= a[left - 1]);
3.1146 +
3.1147 + /*
3.1148 + * Every element from adjoining part plays the role
3.1149 + * of sentinel, therefore this allows us to avoid the
3.1150 + * left range check on each iteration. Moreover, we use
3.1151 + * the more optimized algorithm, so called pair insertion
3.1152 + * sort, which is faster (in the context of Quicksort)
3.1153 + * than traditional implementation of insertion sort.
3.1154 + */
3.1155 + for (int k = left; ++left <= right; k = ++left) {
3.1156 + short a1 = a[k], a2 = a[left];
3.1157 +
3.1158 + if (a1 < a2) {
3.1159 + a2 = a1; a1 = a[left];
3.1160 + }
3.1161 + while (a1 < a[--k]) {
3.1162 + a[k + 2] = a[k];
3.1163 + }
3.1164 + a[++k + 1] = a1;
3.1165 +
3.1166 + while (a2 < a[--k]) {
3.1167 + a[k + 1] = a[k];
3.1168 + }
3.1169 + a[k + 1] = a2;
3.1170 + }
3.1171 + short last = a[right];
3.1172 +
3.1173 + while (last < a[--right]) {
3.1174 + a[right + 1] = a[right];
3.1175 + }
3.1176 + a[right + 1] = last;
3.1177 + }
3.1178 + return;
3.1179 + }
3.1180 +
3.1181 + // Inexpensive approximation of length / 7
3.1182 + int seventh = (length >> 3) + (length >> 6) + 1;
3.1183 +
3.1184 + /*
3.1185 + * Sort five evenly spaced elements around (and including) the
3.1186 + * center element in the range. These elements will be used for
3.1187 + * pivot selection as described below. The choice for spacing
3.1188 + * these elements was empirically determined to work well on
3.1189 + * a wide variety of inputs.
3.1190 + */
3.1191 + int e3 = (left + right) >>> 1; // The midpoint
3.1192 + int e2 = e3 - seventh;
3.1193 + int e1 = e2 - seventh;
3.1194 + int e4 = e3 + seventh;
3.1195 + int e5 = e4 + seventh;
3.1196 +
3.1197 + // Sort these elements using insertion sort
3.1198 + if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.1199 +
3.1200 + if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.1201 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1202 + }
3.1203 + if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.1204 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.1205 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1206 + }
3.1207 + }
3.1208 + if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.1209 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.1210 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.1211 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1212 + }
3.1213 + }
3.1214 + }
3.1215 +
3.1216 + // Pointers
3.1217 + int less = left; // The index of the first element of center part
3.1218 + int great = right; // The index before the first element of right part
3.1219 +
3.1220 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.1221 + /*
3.1222 + * Use the second and fourth of the five sorted elements as pivots.
3.1223 + * These values are inexpensive approximations of the first and
3.1224 + * second terciles of the array. Note that pivot1 <= pivot2.
3.1225 + */
3.1226 + short pivot1 = a[e2];
3.1227 + short pivot2 = a[e4];
3.1228 +
3.1229 + /*
3.1230 + * The first and the last elements to be sorted are moved to the
3.1231 + * locations formerly occupied by the pivots. When partitioning
3.1232 + * is complete, the pivots are swapped back into their final
3.1233 + * positions, and excluded from subsequent sorting.
3.1234 + */
3.1235 + a[e2] = a[left];
3.1236 + a[e4] = a[right];
3.1237 +
3.1238 + /*
3.1239 + * Skip elements, which are less or greater than pivot values.
3.1240 + */
3.1241 + while (a[++less] < pivot1);
3.1242 + while (a[--great] > pivot2);
3.1243 +
3.1244 + /*
3.1245 + * Partitioning:
3.1246 + *
3.1247 + * left part center part right part
3.1248 + * +--------------------------------------------------------------+
3.1249 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.1250 + * +--------------------------------------------------------------+
3.1251 + * ^ ^ ^
3.1252 + * | | |
3.1253 + * less k great
3.1254 + *
3.1255 + * Invariants:
3.1256 + *
3.1257 + * all in (left, less) < pivot1
3.1258 + * pivot1 <= all in [less, k) <= pivot2
3.1259 + * all in (great, right) > pivot2
3.1260 + *
3.1261 + * Pointer k is the first index of ?-part.
3.1262 + */
3.1263 + outer:
3.1264 + for (int k = less - 1; ++k <= great; ) {
3.1265 + short ak = a[k];
3.1266 + if (ak < pivot1) { // Move a[k] to left part
3.1267 + a[k] = a[less];
3.1268 + /*
3.1269 + * Here and below we use "a[i] = b; i++;" instead
3.1270 + * of "a[i++] = b;" due to performance issue.
3.1271 + */
3.1272 + a[less] = ak;
3.1273 + ++less;
3.1274 + } else if (ak > pivot2) { // Move a[k] to right part
3.1275 + while (a[great] > pivot2) {
3.1276 + if (great-- == k) {
3.1277 + break outer;
3.1278 + }
3.1279 + }
3.1280 + if (a[great] < pivot1) { // a[great] <= pivot2
3.1281 + a[k] = a[less];
3.1282 + a[less] = a[great];
3.1283 + ++less;
3.1284 + } else { // pivot1 <= a[great] <= pivot2
3.1285 + a[k] = a[great];
3.1286 + }
3.1287 + /*
3.1288 + * Here and below we use "a[i] = b; i--;" instead
3.1289 + * of "a[i--] = b;" due to performance issue.
3.1290 + */
3.1291 + a[great] = ak;
3.1292 + --great;
3.1293 + }
3.1294 + }
3.1295 +
3.1296 + // Swap pivots into their final positions
3.1297 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.1298 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.1299 +
3.1300 + // Sort left and right parts recursively, excluding known pivots
3.1301 + sort(a, left, less - 2, leftmost);
3.1302 + sort(a, great + 2, right, false);
3.1303 +
3.1304 + /*
3.1305 + * If center part is too large (comprises > 4/7 of the array),
3.1306 + * swap internal pivot values to ends.
3.1307 + */
3.1308 + if (less < e1 && e5 < great) {
3.1309 + /*
3.1310 + * Skip elements, which are equal to pivot values.
3.1311 + */
3.1312 + while (a[less] == pivot1) {
3.1313 + ++less;
3.1314 + }
3.1315 +
3.1316 + while (a[great] == pivot2) {
3.1317 + --great;
3.1318 + }
3.1319 +
3.1320 + /*
3.1321 + * Partitioning:
3.1322 + *
3.1323 + * left part center part right part
3.1324 + * +----------------------------------------------------------+
3.1325 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.1326 + * +----------------------------------------------------------+
3.1327 + * ^ ^ ^
3.1328 + * | | |
3.1329 + * less k great
3.1330 + *
3.1331 + * Invariants:
3.1332 + *
3.1333 + * all in (*, less) == pivot1
3.1334 + * pivot1 < all in [less, k) < pivot2
3.1335 + * all in (great, *) == pivot2
3.1336 + *
3.1337 + * Pointer k is the first index of ?-part.
3.1338 + */
3.1339 + outer:
3.1340 + for (int k = less - 1; ++k <= great; ) {
3.1341 + short ak = a[k];
3.1342 + if (ak == pivot1) { // Move a[k] to left part
3.1343 + a[k] = a[less];
3.1344 + a[less] = ak;
3.1345 + ++less;
3.1346 + } else if (ak == pivot2) { // Move a[k] to right part
3.1347 + while (a[great] == pivot2) {
3.1348 + if (great-- == k) {
3.1349 + break outer;
3.1350 + }
3.1351 + }
3.1352 + if (a[great] == pivot1) { // a[great] < pivot2
3.1353 + a[k] = a[less];
3.1354 + /*
3.1355 + * Even though a[great] equals to pivot1, the
3.1356 + * assignment a[less] = pivot1 may be incorrect,
3.1357 + * if a[great] and pivot1 are floating-point zeros
3.1358 + * of different signs. Therefore in float and
3.1359 + * double sorting methods we have to use more
3.1360 + * accurate assignment a[less] = a[great].
3.1361 + */
3.1362 + a[less] = pivot1;
3.1363 + ++less;
3.1364 + } else { // pivot1 < a[great] < pivot2
3.1365 + a[k] = a[great];
3.1366 + }
3.1367 + a[great] = ak;
3.1368 + --great;
3.1369 + }
3.1370 + }
3.1371 + }
3.1372 +
3.1373 + // Sort center part recursively
3.1374 + sort(a, less, great, false);
3.1375 +
3.1376 + } else { // Partitioning with one pivot
3.1377 + /*
3.1378 + * Use the third of the five sorted elements as pivot.
3.1379 + * This value is inexpensive approximation of the median.
3.1380 + */
3.1381 + short pivot = a[e3];
3.1382 +
3.1383 + /*
3.1384 + * Partitioning degenerates to the traditional 3-way
3.1385 + * (or "Dutch National Flag") schema:
3.1386 + *
3.1387 + * left part center part right part
3.1388 + * +-------------------------------------------------+
3.1389 + * | < pivot | == pivot | ? | > pivot |
3.1390 + * +-------------------------------------------------+
3.1391 + * ^ ^ ^
3.1392 + * | | |
3.1393 + * less k great
3.1394 + *
3.1395 + * Invariants:
3.1396 + *
3.1397 + * all in (left, less) < pivot
3.1398 + * all in [less, k) == pivot
3.1399 + * all in (great, right) > pivot
3.1400 + *
3.1401 + * Pointer k is the first index of ?-part.
3.1402 + */
3.1403 + for (int k = less; k <= great; ++k) {
3.1404 + if (a[k] == pivot) {
3.1405 + continue;
3.1406 + }
3.1407 + short ak = a[k];
3.1408 + if (ak < pivot) { // Move a[k] to left part
3.1409 + a[k] = a[less];
3.1410 + a[less] = ak;
3.1411 + ++less;
3.1412 + } else { // a[k] > pivot - Move a[k] to right part
3.1413 + while (a[great] > pivot) {
3.1414 + --great;
3.1415 + }
3.1416 + if (a[great] < pivot) { // a[great] <= pivot
3.1417 + a[k] = a[less];
3.1418 + a[less] = a[great];
3.1419 + ++less;
3.1420 + } else { // a[great] == pivot
3.1421 + /*
3.1422 + * Even though a[great] equals to pivot, the
3.1423 + * assignment a[k] = pivot may be incorrect,
3.1424 + * if a[great] and pivot are floating-point
3.1425 + * zeros of different signs. Therefore in float
3.1426 + * and double sorting methods we have to use
3.1427 + * more accurate assignment a[k] = a[great].
3.1428 + */
3.1429 + a[k] = pivot;
3.1430 + }
3.1431 + a[great] = ak;
3.1432 + --great;
3.1433 + }
3.1434 + }
3.1435 +
3.1436 + /*
3.1437 + * Sort left and right parts recursively.
3.1438 + * All elements from center part are equal
3.1439 + * and, therefore, already sorted.
3.1440 + */
3.1441 + sort(a, left, less - 1, leftmost);
3.1442 + sort(a, great + 1, right, false);
3.1443 + }
3.1444 + }
3.1445 +
3.1446 + /**
3.1447 + * Sorts the specified array.
3.1448 + *
3.1449 + * @param a the array to be sorted
3.1450 + */
3.1451 + public static void sort(char[] a) {
3.1452 + sort(a, 0, a.length - 1);
3.1453 + }
3.1454 +
3.1455 + /**
3.1456 + * Sorts the specified range of the array.
3.1457 + *
3.1458 + * @param a the array to be sorted
3.1459 + * @param left the index of the first element, inclusive, to be sorted
3.1460 + * @param right the index of the last element, inclusive, to be sorted
3.1461 + */
3.1462 + public static void sort(char[] a, int left, int right) {
3.1463 + // Use counting sort on large arrays
3.1464 + if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
3.1465 + int[] count = new int[NUM_CHAR_VALUES];
3.1466 +
3.1467 + for (int i = left - 1; ++i <= right;
3.1468 + count[a[i]]++
3.1469 + );
3.1470 + for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
3.1471 + while (count[--i] == 0);
3.1472 + char value = (char) i;
3.1473 + int s = count[i];
3.1474 +
3.1475 + do {
3.1476 + a[--k] = value;
3.1477 + } while (--s > 0);
3.1478 + }
3.1479 + } else { // Use Dual-Pivot Quicksort on small arrays
3.1480 + doSort(a, left, right);
3.1481 + }
3.1482 + }
3.1483 +
3.1484 + /** The number of distinct char values. */
3.1485 + private static final int NUM_CHAR_VALUES = 1 << 16;
3.1486 +
3.1487 + /**
3.1488 + * Sorts the specified range of the array.
3.1489 + *
3.1490 + * @param a the array to be sorted
3.1491 + * @param left the index of the first element, inclusive, to be sorted
3.1492 + * @param right the index of the last element, inclusive, to be sorted
3.1493 + */
3.1494 + private static void doSort(char[] a, int left, int right) {
3.1495 + // Use Quicksort on small arrays
3.1496 + if (right - left < QUICKSORT_THRESHOLD) {
3.1497 + sort(a, left, right, true);
3.1498 + return;
3.1499 + }
3.1500 +
3.1501 + /*
3.1502 + * Index run[i] is the start of i-th run
3.1503 + * (ascending or descending sequence).
3.1504 + */
3.1505 + int[] run = new int[MAX_RUN_COUNT + 1];
3.1506 + int count = 0; run[0] = left;
3.1507 +
3.1508 + // Check if the array is nearly sorted
3.1509 + for (int k = left; k < right; run[count] = k) {
3.1510 + if (a[k] < a[k + 1]) { // ascending
3.1511 + while (++k <= right && a[k - 1] <= a[k]);
3.1512 + } else if (a[k] > a[k + 1]) { // descending
3.1513 + while (++k <= right && a[k - 1] >= a[k]);
3.1514 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.1515 + char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.1516 + }
3.1517 + } else { // equal
3.1518 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.1519 + if (--m == 0) {
3.1520 + sort(a, left, right, true);
3.1521 + return;
3.1522 + }
3.1523 + }
3.1524 + }
3.1525 +
3.1526 + /*
3.1527 + * The array is not highly structured,
3.1528 + * use Quicksort instead of merge sort.
3.1529 + */
3.1530 + if (++count == MAX_RUN_COUNT) {
3.1531 + sort(a, left, right, true);
3.1532 + return;
3.1533 + }
3.1534 + }
3.1535 +
3.1536 + // Check special cases
3.1537 + if (run[count] == right++) { // The last run contains one element
3.1538 + run[++count] = right;
3.1539 + } else if (count == 1) { // The array is already sorted
3.1540 + return;
3.1541 + }
3.1542 +
3.1543 + /*
3.1544 + * Create temporary array, which is used for merging.
3.1545 + * Implementation note: variable "right" is increased by 1.
3.1546 + */
3.1547 + char[] b; byte odd = 0;
3.1548 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.1549 +
3.1550 + if (odd == 0) {
3.1551 + b = a; a = new char[b.length];
3.1552 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.1553 + } else {
3.1554 + b = new char[a.length];
3.1555 + }
3.1556 +
3.1557 + // Merging
3.1558 + for (int last; count > 1; count = last) {
3.1559 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.1560 + int hi = run[k], mi = run[k - 1];
3.1561 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.1562 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.1563 + b[i] = a[p++];
3.1564 + } else {
3.1565 + b[i] = a[q++];
3.1566 + }
3.1567 + }
3.1568 + run[++last] = hi;
3.1569 + }
3.1570 + if ((count & 1) != 0) {
3.1571 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.1572 + b[i] = a[i]
3.1573 + );
3.1574 + run[++last] = right;
3.1575 + }
3.1576 + char[] t = a; a = b; b = t;
3.1577 + }
3.1578 + }
3.1579 +
3.1580 + /**
3.1581 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.1582 + *
3.1583 + * @param a the array to be sorted
3.1584 + * @param left the index of the first element, inclusive, to be sorted
3.1585 + * @param right the index of the last element, inclusive, to be sorted
3.1586 + * @param leftmost indicates if this part is the leftmost in the range
3.1587 + */
3.1588 + private static void sort(char[] a, int left, int right, boolean leftmost) {
3.1589 + int length = right - left + 1;
3.1590 +
3.1591 + // Use insertion sort on tiny arrays
3.1592 + if (length < INSERTION_SORT_THRESHOLD) {
3.1593 + if (leftmost) {
3.1594 + /*
3.1595 + * Traditional (without sentinel) insertion sort,
3.1596 + * optimized for server VM, is used in case of
3.1597 + * the leftmost part.
3.1598 + */
3.1599 + for (int i = left, j = i; i < right; j = ++i) {
3.1600 + char ai = a[i + 1];
3.1601 + while (ai < a[j]) {
3.1602 + a[j + 1] = a[j];
3.1603 + if (j-- == left) {
3.1604 + break;
3.1605 + }
3.1606 + }
3.1607 + a[j + 1] = ai;
3.1608 + }
3.1609 + } else {
3.1610 + /*
3.1611 + * Skip the longest ascending sequence.
3.1612 + */
3.1613 + do {
3.1614 + if (left >= right) {
3.1615 + return;
3.1616 + }
3.1617 + } while (a[++left] >= a[left - 1]);
3.1618 +
3.1619 + /*
3.1620 + * Every element from adjoining part plays the role
3.1621 + * of sentinel, therefore this allows us to avoid the
3.1622 + * left range check on each iteration. Moreover, we use
3.1623 + * the more optimized algorithm, so called pair insertion
3.1624 + * sort, which is faster (in the context of Quicksort)
3.1625 + * than traditional implementation of insertion sort.
3.1626 + */
3.1627 + for (int k = left; ++left <= right; k = ++left) {
3.1628 + char a1 = a[k], a2 = a[left];
3.1629 +
3.1630 + if (a1 < a2) {
3.1631 + a2 = a1; a1 = a[left];
3.1632 + }
3.1633 + while (a1 < a[--k]) {
3.1634 + a[k + 2] = a[k];
3.1635 + }
3.1636 + a[++k + 1] = a1;
3.1637 +
3.1638 + while (a2 < a[--k]) {
3.1639 + a[k + 1] = a[k];
3.1640 + }
3.1641 + a[k + 1] = a2;
3.1642 + }
3.1643 + char last = a[right];
3.1644 +
3.1645 + while (last < a[--right]) {
3.1646 + a[right + 1] = a[right];
3.1647 + }
3.1648 + a[right + 1] = last;
3.1649 + }
3.1650 + return;
3.1651 + }
3.1652 +
3.1653 + // Inexpensive approximation of length / 7
3.1654 + int seventh = (length >> 3) + (length >> 6) + 1;
3.1655 +
3.1656 + /*
3.1657 + * Sort five evenly spaced elements around (and including) the
3.1658 + * center element in the range. These elements will be used for
3.1659 + * pivot selection as described below. The choice for spacing
3.1660 + * these elements was empirically determined to work well on
3.1661 + * a wide variety of inputs.
3.1662 + */
3.1663 + int e3 = (left + right) >>> 1; // The midpoint
3.1664 + int e2 = e3 - seventh;
3.1665 + int e1 = e2 - seventh;
3.1666 + int e4 = e3 + seventh;
3.1667 + int e5 = e4 + seventh;
3.1668 +
3.1669 + // Sort these elements using insertion sort
3.1670 + if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.1671 +
3.1672 + if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.1673 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1674 + }
3.1675 + if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.1676 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.1677 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1678 + }
3.1679 + }
3.1680 + if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.1681 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.1682 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.1683 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.1684 + }
3.1685 + }
3.1686 + }
3.1687 +
3.1688 + // Pointers
3.1689 + int less = left; // The index of the first element of center part
3.1690 + int great = right; // The index before the first element of right part
3.1691 +
3.1692 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.1693 + /*
3.1694 + * Use the second and fourth of the five sorted elements as pivots.
3.1695 + * These values are inexpensive approximations of the first and
3.1696 + * second terciles of the array. Note that pivot1 <= pivot2.
3.1697 + */
3.1698 + char pivot1 = a[e2];
3.1699 + char pivot2 = a[e4];
3.1700 +
3.1701 + /*
3.1702 + * The first and the last elements to be sorted are moved to the
3.1703 + * locations formerly occupied by the pivots. When partitioning
3.1704 + * is complete, the pivots are swapped back into their final
3.1705 + * positions, and excluded from subsequent sorting.
3.1706 + */
3.1707 + a[e2] = a[left];
3.1708 + a[e4] = a[right];
3.1709 +
3.1710 + /*
3.1711 + * Skip elements, which are less or greater than pivot values.
3.1712 + */
3.1713 + while (a[++less] < pivot1);
3.1714 + while (a[--great] > pivot2);
3.1715 +
3.1716 + /*
3.1717 + * Partitioning:
3.1718 + *
3.1719 + * left part center part right part
3.1720 + * +--------------------------------------------------------------+
3.1721 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.1722 + * +--------------------------------------------------------------+
3.1723 + * ^ ^ ^
3.1724 + * | | |
3.1725 + * less k great
3.1726 + *
3.1727 + * Invariants:
3.1728 + *
3.1729 + * all in (left, less) < pivot1
3.1730 + * pivot1 <= all in [less, k) <= pivot2
3.1731 + * all in (great, right) > pivot2
3.1732 + *
3.1733 + * Pointer k is the first index of ?-part.
3.1734 + */
3.1735 + outer:
3.1736 + for (int k = less - 1; ++k <= great; ) {
3.1737 + char ak = a[k];
3.1738 + if (ak < pivot1) { // Move a[k] to left part
3.1739 + a[k] = a[less];
3.1740 + /*
3.1741 + * Here and below we use "a[i] = b; i++;" instead
3.1742 + * of "a[i++] = b;" due to performance issue.
3.1743 + */
3.1744 + a[less] = ak;
3.1745 + ++less;
3.1746 + } else if (ak > pivot2) { // Move a[k] to right part
3.1747 + while (a[great] > pivot2) {
3.1748 + if (great-- == k) {
3.1749 + break outer;
3.1750 + }
3.1751 + }
3.1752 + if (a[great] < pivot1) { // a[great] <= pivot2
3.1753 + a[k] = a[less];
3.1754 + a[less] = a[great];
3.1755 + ++less;
3.1756 + } else { // pivot1 <= a[great] <= pivot2
3.1757 + a[k] = a[great];
3.1758 + }
3.1759 + /*
3.1760 + * Here and below we use "a[i] = b; i--;" instead
3.1761 + * of "a[i--] = b;" due to performance issue.
3.1762 + */
3.1763 + a[great] = ak;
3.1764 + --great;
3.1765 + }
3.1766 + }
3.1767 +
3.1768 + // Swap pivots into their final positions
3.1769 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.1770 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.1771 +
3.1772 + // Sort left and right parts recursively, excluding known pivots
3.1773 + sort(a, left, less - 2, leftmost);
3.1774 + sort(a, great + 2, right, false);
3.1775 +
3.1776 + /*
3.1777 + * If center part is too large (comprises > 4/7 of the array),
3.1778 + * swap internal pivot values to ends.
3.1779 + */
3.1780 + if (less < e1 && e5 < great) {
3.1781 + /*
3.1782 + * Skip elements, which are equal to pivot values.
3.1783 + */
3.1784 + while (a[less] == pivot1) {
3.1785 + ++less;
3.1786 + }
3.1787 +
3.1788 + while (a[great] == pivot2) {
3.1789 + --great;
3.1790 + }
3.1791 +
3.1792 + /*
3.1793 + * Partitioning:
3.1794 + *
3.1795 + * left part center part right part
3.1796 + * +----------------------------------------------------------+
3.1797 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.1798 + * +----------------------------------------------------------+
3.1799 + * ^ ^ ^
3.1800 + * | | |
3.1801 + * less k great
3.1802 + *
3.1803 + * Invariants:
3.1804 + *
3.1805 + * all in (*, less) == pivot1
3.1806 + * pivot1 < all in [less, k) < pivot2
3.1807 + * all in (great, *) == pivot2
3.1808 + *
3.1809 + * Pointer k is the first index of ?-part.
3.1810 + */
3.1811 + outer:
3.1812 + for (int k = less - 1; ++k <= great; ) {
3.1813 + char ak = a[k];
3.1814 + if (ak == pivot1) { // Move a[k] to left part
3.1815 + a[k] = a[less];
3.1816 + a[less] = ak;
3.1817 + ++less;
3.1818 + } else if (ak == pivot2) { // Move a[k] to right part
3.1819 + while (a[great] == pivot2) {
3.1820 + if (great-- == k) {
3.1821 + break outer;
3.1822 + }
3.1823 + }
3.1824 + if (a[great] == pivot1) { // a[great] < pivot2
3.1825 + a[k] = a[less];
3.1826 + /*
3.1827 + * Even though a[great] equals to pivot1, the
3.1828 + * assignment a[less] = pivot1 may be incorrect,
3.1829 + * if a[great] and pivot1 are floating-point zeros
3.1830 + * of different signs. Therefore in float and
3.1831 + * double sorting methods we have to use more
3.1832 + * accurate assignment a[less] = a[great].
3.1833 + */
3.1834 + a[less] = pivot1;
3.1835 + ++less;
3.1836 + } else { // pivot1 < a[great] < pivot2
3.1837 + a[k] = a[great];
3.1838 + }
3.1839 + a[great] = ak;
3.1840 + --great;
3.1841 + }
3.1842 + }
3.1843 + }
3.1844 +
3.1845 + // Sort center part recursively
3.1846 + sort(a, less, great, false);
3.1847 +
3.1848 + } else { // Partitioning with one pivot
3.1849 + /*
3.1850 + * Use the third of the five sorted elements as pivot.
3.1851 + * This value is inexpensive approximation of the median.
3.1852 + */
3.1853 + char pivot = a[e3];
3.1854 +
3.1855 + /*
3.1856 + * Partitioning degenerates to the traditional 3-way
3.1857 + * (or "Dutch National Flag") schema:
3.1858 + *
3.1859 + * left part center part right part
3.1860 + * +-------------------------------------------------+
3.1861 + * | < pivot | == pivot | ? | > pivot |
3.1862 + * +-------------------------------------------------+
3.1863 + * ^ ^ ^
3.1864 + * | | |
3.1865 + * less k great
3.1866 + *
3.1867 + * Invariants:
3.1868 + *
3.1869 + * all in (left, less) < pivot
3.1870 + * all in [less, k) == pivot
3.1871 + * all in (great, right) > pivot
3.1872 + *
3.1873 + * Pointer k is the first index of ?-part.
3.1874 + */
3.1875 + for (int k = less; k <= great; ++k) {
3.1876 + if (a[k] == pivot) {
3.1877 + continue;
3.1878 + }
3.1879 + char ak = a[k];
3.1880 + if (ak < pivot) { // Move a[k] to left part
3.1881 + a[k] = a[less];
3.1882 + a[less] = ak;
3.1883 + ++less;
3.1884 + } else { // a[k] > pivot - Move a[k] to right part
3.1885 + while (a[great] > pivot) {
3.1886 + --great;
3.1887 + }
3.1888 + if (a[great] < pivot) { // a[great] <= pivot
3.1889 + a[k] = a[less];
3.1890 + a[less] = a[great];
3.1891 + ++less;
3.1892 + } else { // a[great] == pivot
3.1893 + /*
3.1894 + * Even though a[great] equals to pivot, the
3.1895 + * assignment a[k] = pivot may be incorrect,
3.1896 + * if a[great] and pivot are floating-point
3.1897 + * zeros of different signs. Therefore in float
3.1898 + * and double sorting methods we have to use
3.1899 + * more accurate assignment a[k] = a[great].
3.1900 + */
3.1901 + a[k] = pivot;
3.1902 + }
3.1903 + a[great] = ak;
3.1904 + --great;
3.1905 + }
3.1906 + }
3.1907 +
3.1908 + /*
3.1909 + * Sort left and right parts recursively.
3.1910 + * All elements from center part are equal
3.1911 + * and, therefore, already sorted.
3.1912 + */
3.1913 + sort(a, left, less - 1, leftmost);
3.1914 + sort(a, great + 1, right, false);
3.1915 + }
3.1916 + }
3.1917 +
3.1918 + /** The number of distinct byte values. */
3.1919 + private static final int NUM_BYTE_VALUES = 1 << 8;
3.1920 +
3.1921 + /**
3.1922 + * Sorts the specified array.
3.1923 + *
3.1924 + * @param a the array to be sorted
3.1925 + */
3.1926 + public static void sort(byte[] a) {
3.1927 + sort(a, 0, a.length - 1);
3.1928 + }
3.1929 +
3.1930 + /**
3.1931 + * Sorts the specified range of the array.
3.1932 + *
3.1933 + * @param a the array to be sorted
3.1934 + * @param left the index of the first element, inclusive, to be sorted
3.1935 + * @param right the index of the last element, inclusive, to be sorted
3.1936 + */
3.1937 + public static void sort(byte[] a, int left, int right) {
3.1938 + // Use counting sort on large arrays
3.1939 + if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
3.1940 + int[] count = new int[NUM_BYTE_VALUES];
3.1941 +
3.1942 + for (int i = left - 1; ++i <= right;
3.1943 + count[a[i] - Byte.MIN_VALUE]++
3.1944 + );
3.1945 + for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
3.1946 + while (count[--i] == 0);
3.1947 + byte value = (byte) (i + Byte.MIN_VALUE);
3.1948 + int s = count[i];
3.1949 +
3.1950 + do {
3.1951 + a[--k] = value;
3.1952 + } while (--s > 0);
3.1953 + }
3.1954 + } else { // Use insertion sort on small arrays
3.1955 + for (int i = left, j = i; i < right; j = ++i) {
3.1956 + byte ai = a[i + 1];
3.1957 + while (ai < a[j]) {
3.1958 + a[j + 1] = a[j];
3.1959 + if (j-- == left) {
3.1960 + break;
3.1961 + }
3.1962 + }
3.1963 + a[j + 1] = ai;
3.1964 + }
3.1965 + }
3.1966 + }
3.1967 +
3.1968 + /**
3.1969 + * Sorts the specified array.
3.1970 + *
3.1971 + * @param a the array to be sorted
3.1972 + */
3.1973 + public static void sort(float[] a) {
3.1974 + sort(a, 0, a.length - 1);
3.1975 + }
3.1976 +
3.1977 + /**
3.1978 + * Sorts the specified range of the array.
3.1979 + *
3.1980 + * @param a the array to be sorted
3.1981 + * @param left the index of the first element, inclusive, to be sorted
3.1982 + * @param right the index of the last element, inclusive, to be sorted
3.1983 + */
3.1984 + public static void sort(float[] a, int left, int right) {
3.1985 + /*
3.1986 + * Phase 1: Move NaNs to the end of the array.
3.1987 + */
3.1988 + while (left <= right && Float.isNaN(a[right])) {
3.1989 + --right;
3.1990 + }
3.1991 + for (int k = right; --k >= left; ) {
3.1992 + float ak = a[k];
3.1993 + if (ak != ak) { // a[k] is NaN
3.1994 + a[k] = a[right];
3.1995 + a[right] = ak;
3.1996 + --right;
3.1997 + }
3.1998 + }
3.1999 +
3.2000 + /*
3.2001 + * Phase 2: Sort everything except NaNs (which are already in place).
3.2002 + */
3.2003 + doSort(a, left, right);
3.2004 +
3.2005 + /*
3.2006 + * Phase 3: Place negative zeros before positive zeros.
3.2007 + */
3.2008 + int hi = right;
3.2009 +
3.2010 + /*
3.2011 + * Find the first zero, or first positive, or last negative element.
3.2012 + */
3.2013 + while (left < hi) {
3.2014 + int middle = (left + hi) >>> 1;
3.2015 + float middleValue = a[middle];
3.2016 +
3.2017 + if (middleValue < 0.0f) {
3.2018 + left = middle + 1;
3.2019 + } else {
3.2020 + hi = middle;
3.2021 + }
3.2022 + }
3.2023 +
3.2024 + /*
3.2025 + * Skip the last negative value (if any) or all leading negative zeros.
3.2026 + */
3.2027 + while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
3.2028 + ++left;
3.2029 + }
3.2030 +
3.2031 + /*
3.2032 + * Move negative zeros to the beginning of the sub-range.
3.2033 + *
3.2034 + * Partitioning:
3.2035 + *
3.2036 + * +----------------------------------------------------+
3.2037 + * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
3.2038 + * +----------------------------------------------------+
3.2039 + * ^ ^ ^
3.2040 + * | | |
3.2041 + * left p k
3.2042 + *
3.2043 + * Invariants:
3.2044 + *
3.2045 + * all in (*, left) < 0.0
3.2046 + * all in [left, p) == -0.0
3.2047 + * all in [p, k) == 0.0
3.2048 + * all in [k, right] >= 0.0
3.2049 + *
3.2050 + * Pointer k is the first index of ?-part.
3.2051 + */
3.2052 + for (int k = left, p = left - 1; ++k <= right; ) {
3.2053 + float ak = a[k];
3.2054 + if (ak != 0.0f) {
3.2055 + break;
3.2056 + }
3.2057 + if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
3.2058 + a[k] = 0.0f;
3.2059 + a[++p] = -0.0f;
3.2060 + }
3.2061 + }
3.2062 + }
3.2063 +
3.2064 + /**
3.2065 + * Sorts the specified range of the array.
3.2066 + *
3.2067 + * @param a the array to be sorted
3.2068 + * @param left the index of the first element, inclusive, to be sorted
3.2069 + * @param right the index of the last element, inclusive, to be sorted
3.2070 + */
3.2071 + private static void doSort(float[] a, int left, int right) {
3.2072 + // Use Quicksort on small arrays
3.2073 + if (right - left < QUICKSORT_THRESHOLD) {
3.2074 + sort(a, left, right, true);
3.2075 + return;
3.2076 + }
3.2077 +
3.2078 + /*
3.2079 + * Index run[i] is the start of i-th run
3.2080 + * (ascending or descending sequence).
3.2081 + */
3.2082 + int[] run = new int[MAX_RUN_COUNT + 1];
3.2083 + int count = 0; run[0] = left;
3.2084 +
3.2085 + // Check if the array is nearly sorted
3.2086 + for (int k = left; k < right; run[count] = k) {
3.2087 + if (a[k] < a[k + 1]) { // ascending
3.2088 + while (++k <= right && a[k - 1] <= a[k]);
3.2089 + } else if (a[k] > a[k + 1]) { // descending
3.2090 + while (++k <= right && a[k - 1] >= a[k]);
3.2091 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.2092 + float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.2093 + }
3.2094 + } else { // equal
3.2095 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.2096 + if (--m == 0) {
3.2097 + sort(a, left, right, true);
3.2098 + return;
3.2099 + }
3.2100 + }
3.2101 + }
3.2102 +
3.2103 + /*
3.2104 + * The array is not highly structured,
3.2105 + * use Quicksort instead of merge sort.
3.2106 + */
3.2107 + if (++count == MAX_RUN_COUNT) {
3.2108 + sort(a, left, right, true);
3.2109 + return;
3.2110 + }
3.2111 + }
3.2112 +
3.2113 + // Check special cases
3.2114 + if (run[count] == right++) { // The last run contains one element
3.2115 + run[++count] = right;
3.2116 + } else if (count == 1) { // The array is already sorted
3.2117 + return;
3.2118 + }
3.2119 +
3.2120 + /*
3.2121 + * Create temporary array, which is used for merging.
3.2122 + * Implementation note: variable "right" is increased by 1.
3.2123 + */
3.2124 + float[] b; byte odd = 0;
3.2125 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.2126 +
3.2127 + if (odd == 0) {
3.2128 + b = a; a = new float[b.length];
3.2129 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.2130 + } else {
3.2131 + b = new float[a.length];
3.2132 + }
3.2133 +
3.2134 + // Merging
3.2135 + for (int last; count > 1; count = last) {
3.2136 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.2137 + int hi = run[k], mi = run[k - 1];
3.2138 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.2139 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.2140 + b[i] = a[p++];
3.2141 + } else {
3.2142 + b[i] = a[q++];
3.2143 + }
3.2144 + }
3.2145 + run[++last] = hi;
3.2146 + }
3.2147 + if ((count & 1) != 0) {
3.2148 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.2149 + b[i] = a[i]
3.2150 + );
3.2151 + run[++last] = right;
3.2152 + }
3.2153 + float[] t = a; a = b; b = t;
3.2154 + }
3.2155 + }
3.2156 +
3.2157 + /**
3.2158 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.2159 + *
3.2160 + * @param a the array to be sorted
3.2161 + * @param left the index of the first element, inclusive, to be sorted
3.2162 + * @param right the index of the last element, inclusive, to be sorted
3.2163 + * @param leftmost indicates if this part is the leftmost in the range
3.2164 + */
3.2165 + private static void sort(float[] a, int left, int right, boolean leftmost) {
3.2166 + int length = right - left + 1;
3.2167 +
3.2168 + // Use insertion sort on tiny arrays
3.2169 + if (length < INSERTION_SORT_THRESHOLD) {
3.2170 + if (leftmost) {
3.2171 + /*
3.2172 + * Traditional (without sentinel) insertion sort,
3.2173 + * optimized for server VM, is used in case of
3.2174 + * the leftmost part.
3.2175 + */
3.2176 + for (int i = left, j = i; i < right; j = ++i) {
3.2177 + float ai = a[i + 1];
3.2178 + while (ai < a[j]) {
3.2179 + a[j + 1] = a[j];
3.2180 + if (j-- == left) {
3.2181 + break;
3.2182 + }
3.2183 + }
3.2184 + a[j + 1] = ai;
3.2185 + }
3.2186 + } else {
3.2187 + /*
3.2188 + * Skip the longest ascending sequence.
3.2189 + */
3.2190 + do {
3.2191 + if (left >= right) {
3.2192 + return;
3.2193 + }
3.2194 + } while (a[++left] >= a[left - 1]);
3.2195 +
3.2196 + /*
3.2197 + * Every element from adjoining part plays the role
3.2198 + * of sentinel, therefore this allows us to avoid the
3.2199 + * left range check on each iteration. Moreover, we use
3.2200 + * the more optimized algorithm, so called pair insertion
3.2201 + * sort, which is faster (in the context of Quicksort)
3.2202 + * than traditional implementation of insertion sort.
3.2203 + */
3.2204 + for (int k = left; ++left <= right; k = ++left) {
3.2205 + float a1 = a[k], a2 = a[left];
3.2206 +
3.2207 + if (a1 < a2) {
3.2208 + a2 = a1; a1 = a[left];
3.2209 + }
3.2210 + while (a1 < a[--k]) {
3.2211 + a[k + 2] = a[k];
3.2212 + }
3.2213 + a[++k + 1] = a1;
3.2214 +
3.2215 + while (a2 < a[--k]) {
3.2216 + a[k + 1] = a[k];
3.2217 + }
3.2218 + a[k + 1] = a2;
3.2219 + }
3.2220 + float last = a[right];
3.2221 +
3.2222 + while (last < a[--right]) {
3.2223 + a[right + 1] = a[right];
3.2224 + }
3.2225 + a[right + 1] = last;
3.2226 + }
3.2227 + return;
3.2228 + }
3.2229 +
3.2230 + // Inexpensive approximation of length / 7
3.2231 + int seventh = (length >> 3) + (length >> 6) + 1;
3.2232 +
3.2233 + /*
3.2234 + * Sort five evenly spaced elements around (and including) the
3.2235 + * center element in the range. These elements will be used for
3.2236 + * pivot selection as described below. The choice for spacing
3.2237 + * these elements was empirically determined to work well on
3.2238 + * a wide variety of inputs.
3.2239 + */
3.2240 + int e3 = (left + right) >>> 1; // The midpoint
3.2241 + int e2 = e3 - seventh;
3.2242 + int e1 = e2 - seventh;
3.2243 + int e4 = e3 + seventh;
3.2244 + int e5 = e4 + seventh;
3.2245 +
3.2246 + // Sort these elements using insertion sort
3.2247 + if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.2248 +
3.2249 + if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.2250 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2251 + }
3.2252 + if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.2253 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.2254 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2255 + }
3.2256 + }
3.2257 + if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.2258 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.2259 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.2260 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2261 + }
3.2262 + }
3.2263 + }
3.2264 +
3.2265 + // Pointers
3.2266 + int less = left; // The index of the first element of center part
3.2267 + int great = right; // The index before the first element of right part
3.2268 +
3.2269 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.2270 + /*
3.2271 + * Use the second and fourth of the five sorted elements as pivots.
3.2272 + * These values are inexpensive approximations of the first and
3.2273 + * second terciles of the array. Note that pivot1 <= pivot2.
3.2274 + */
3.2275 + float pivot1 = a[e2];
3.2276 + float pivot2 = a[e4];
3.2277 +
3.2278 + /*
3.2279 + * The first and the last elements to be sorted are moved to the
3.2280 + * locations formerly occupied by the pivots. When partitioning
3.2281 + * is complete, the pivots are swapped back into their final
3.2282 + * positions, and excluded from subsequent sorting.
3.2283 + */
3.2284 + a[e2] = a[left];
3.2285 + a[e4] = a[right];
3.2286 +
3.2287 + /*
3.2288 + * Skip elements, which are less or greater than pivot values.
3.2289 + */
3.2290 + while (a[++less] < pivot1);
3.2291 + while (a[--great] > pivot2);
3.2292 +
3.2293 + /*
3.2294 + * Partitioning:
3.2295 + *
3.2296 + * left part center part right part
3.2297 + * +--------------------------------------------------------------+
3.2298 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.2299 + * +--------------------------------------------------------------+
3.2300 + * ^ ^ ^
3.2301 + * | | |
3.2302 + * less k great
3.2303 + *
3.2304 + * Invariants:
3.2305 + *
3.2306 + * all in (left, less) < pivot1
3.2307 + * pivot1 <= all in [less, k) <= pivot2
3.2308 + * all in (great, right) > pivot2
3.2309 + *
3.2310 + * Pointer k is the first index of ?-part.
3.2311 + */
3.2312 + outer:
3.2313 + for (int k = less - 1; ++k <= great; ) {
3.2314 + float ak = a[k];
3.2315 + if (ak < pivot1) { // Move a[k] to left part
3.2316 + a[k] = a[less];
3.2317 + /*
3.2318 + * Here and below we use "a[i] = b; i++;" instead
3.2319 + * of "a[i++] = b;" due to performance issue.
3.2320 + */
3.2321 + a[less] = ak;
3.2322 + ++less;
3.2323 + } else if (ak > pivot2) { // Move a[k] to right part
3.2324 + while (a[great] > pivot2) {
3.2325 + if (great-- == k) {
3.2326 + break outer;
3.2327 + }
3.2328 + }
3.2329 + if (a[great] < pivot1) { // a[great] <= pivot2
3.2330 + a[k] = a[less];
3.2331 + a[less] = a[great];
3.2332 + ++less;
3.2333 + } else { // pivot1 <= a[great] <= pivot2
3.2334 + a[k] = a[great];
3.2335 + }
3.2336 + /*
3.2337 + * Here and below we use "a[i] = b; i--;" instead
3.2338 + * of "a[i--] = b;" due to performance issue.
3.2339 + */
3.2340 + a[great] = ak;
3.2341 + --great;
3.2342 + }
3.2343 + }
3.2344 +
3.2345 + // Swap pivots into their final positions
3.2346 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.2347 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.2348 +
3.2349 + // Sort left and right parts recursively, excluding known pivots
3.2350 + sort(a, left, less - 2, leftmost);
3.2351 + sort(a, great + 2, right, false);
3.2352 +
3.2353 + /*
3.2354 + * If center part is too large (comprises > 4/7 of the array),
3.2355 + * swap internal pivot values to ends.
3.2356 + */
3.2357 + if (less < e1 && e5 < great) {
3.2358 + /*
3.2359 + * Skip elements, which are equal to pivot values.
3.2360 + */
3.2361 + while (a[less] == pivot1) {
3.2362 + ++less;
3.2363 + }
3.2364 +
3.2365 + while (a[great] == pivot2) {
3.2366 + --great;
3.2367 + }
3.2368 +
3.2369 + /*
3.2370 + * Partitioning:
3.2371 + *
3.2372 + * left part center part right part
3.2373 + * +----------------------------------------------------------+
3.2374 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.2375 + * +----------------------------------------------------------+
3.2376 + * ^ ^ ^
3.2377 + * | | |
3.2378 + * less k great
3.2379 + *
3.2380 + * Invariants:
3.2381 + *
3.2382 + * all in (*, less) == pivot1
3.2383 + * pivot1 < all in [less, k) < pivot2
3.2384 + * all in (great, *) == pivot2
3.2385 + *
3.2386 + * Pointer k is the first index of ?-part.
3.2387 + */
3.2388 + outer:
3.2389 + for (int k = less - 1; ++k <= great; ) {
3.2390 + float ak = a[k];
3.2391 + if (ak == pivot1) { // Move a[k] to left part
3.2392 + a[k] = a[less];
3.2393 + a[less] = ak;
3.2394 + ++less;
3.2395 + } else if (ak == pivot2) { // Move a[k] to right part
3.2396 + while (a[great] == pivot2) {
3.2397 + if (great-- == k) {
3.2398 + break outer;
3.2399 + }
3.2400 + }
3.2401 + if (a[great] == pivot1) { // a[great] < pivot2
3.2402 + a[k] = a[less];
3.2403 + /*
3.2404 + * Even though a[great] equals to pivot1, the
3.2405 + * assignment a[less] = pivot1 may be incorrect,
3.2406 + * if a[great] and pivot1 are floating-point zeros
3.2407 + * of different signs. Therefore in float and
3.2408 + * double sorting methods we have to use more
3.2409 + * accurate assignment a[less] = a[great].
3.2410 + */
3.2411 + a[less] = a[great];
3.2412 + ++less;
3.2413 + } else { // pivot1 < a[great] < pivot2
3.2414 + a[k] = a[great];
3.2415 + }
3.2416 + a[great] = ak;
3.2417 + --great;
3.2418 + }
3.2419 + }
3.2420 + }
3.2421 +
3.2422 + // Sort center part recursively
3.2423 + sort(a, less, great, false);
3.2424 +
3.2425 + } else { // Partitioning with one pivot
3.2426 + /*
3.2427 + * Use the third of the five sorted elements as pivot.
3.2428 + * This value is inexpensive approximation of the median.
3.2429 + */
3.2430 + float pivot = a[e3];
3.2431 +
3.2432 + /*
3.2433 + * Partitioning degenerates to the traditional 3-way
3.2434 + * (or "Dutch National Flag") schema:
3.2435 + *
3.2436 + * left part center part right part
3.2437 + * +-------------------------------------------------+
3.2438 + * | < pivot | == pivot | ? | > pivot |
3.2439 + * +-------------------------------------------------+
3.2440 + * ^ ^ ^
3.2441 + * | | |
3.2442 + * less k great
3.2443 + *
3.2444 + * Invariants:
3.2445 + *
3.2446 + * all in (left, less) < pivot
3.2447 + * all in [less, k) == pivot
3.2448 + * all in (great, right) > pivot
3.2449 + *
3.2450 + * Pointer k is the first index of ?-part.
3.2451 + */
3.2452 + for (int k = less; k <= great; ++k) {
3.2453 + if (a[k] == pivot) {
3.2454 + continue;
3.2455 + }
3.2456 + float ak = a[k];
3.2457 + if (ak < pivot) { // Move a[k] to left part
3.2458 + a[k] = a[less];
3.2459 + a[less] = ak;
3.2460 + ++less;
3.2461 + } else { // a[k] > pivot - Move a[k] to right part
3.2462 + while (a[great] > pivot) {
3.2463 + --great;
3.2464 + }
3.2465 + if (a[great] < pivot) { // a[great] <= pivot
3.2466 + a[k] = a[less];
3.2467 + a[less] = a[great];
3.2468 + ++less;
3.2469 + } else { // a[great] == pivot
3.2470 + /*
3.2471 + * Even though a[great] equals to pivot, the
3.2472 + * assignment a[k] = pivot may be incorrect,
3.2473 + * if a[great] and pivot are floating-point
3.2474 + * zeros of different signs. Therefore in float
3.2475 + * and double sorting methods we have to use
3.2476 + * more accurate assignment a[k] = a[great].
3.2477 + */
3.2478 + a[k] = a[great];
3.2479 + }
3.2480 + a[great] = ak;
3.2481 + --great;
3.2482 + }
3.2483 + }
3.2484 +
3.2485 + /*
3.2486 + * Sort left and right parts recursively.
3.2487 + * All elements from center part are equal
3.2488 + * and, therefore, already sorted.
3.2489 + */
3.2490 + sort(a, left, less - 1, leftmost);
3.2491 + sort(a, great + 1, right, false);
3.2492 + }
3.2493 + }
3.2494 +
3.2495 + /**
3.2496 + * Sorts the specified array.
3.2497 + *
3.2498 + * @param a the array to be sorted
3.2499 + */
3.2500 + public static void sort(double[] a) {
3.2501 + sort(a, 0, a.length - 1);
3.2502 + }
3.2503 +
3.2504 + /**
3.2505 + * Sorts the specified range of the array.
3.2506 + *
3.2507 + * @param a the array to be sorted
3.2508 + * @param left the index of the first element, inclusive, to be sorted
3.2509 + * @param right the index of the last element, inclusive, to be sorted
3.2510 + */
3.2511 + public static void sort(double[] a, int left, int right) {
3.2512 + /*
3.2513 + * Phase 1: Move NaNs to the end of the array.
3.2514 + */
3.2515 + while (left <= right && Double.isNaN(a[right])) {
3.2516 + --right;
3.2517 + }
3.2518 + for (int k = right; --k >= left; ) {
3.2519 + double ak = a[k];
3.2520 + if (ak != ak) { // a[k] is NaN
3.2521 + a[k] = a[right];
3.2522 + a[right] = ak;
3.2523 + --right;
3.2524 + }
3.2525 + }
3.2526 +
3.2527 + /*
3.2528 + * Phase 2: Sort everything except NaNs (which are already in place).
3.2529 + */
3.2530 + doSort(a, left, right);
3.2531 +
3.2532 + /*
3.2533 + * Phase 3: Place negative zeros before positive zeros.
3.2534 + */
3.2535 + int hi = right;
3.2536 +
3.2537 + /*
3.2538 + * Find the first zero, or first positive, or last negative element.
3.2539 + */
3.2540 + while (left < hi) {
3.2541 + int middle = (left + hi) >>> 1;
3.2542 + double middleValue = a[middle];
3.2543 +
3.2544 + if (middleValue < 0.0d) {
3.2545 + left = middle + 1;
3.2546 + } else {
3.2547 + hi = middle;
3.2548 + }
3.2549 + }
3.2550 +
3.2551 + /*
3.2552 + * Skip the last negative value (if any) or all leading negative zeros.
3.2553 + */
3.2554 + while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
3.2555 + ++left;
3.2556 + }
3.2557 +
3.2558 + /*
3.2559 + * Move negative zeros to the beginning of the sub-range.
3.2560 + *
3.2561 + * Partitioning:
3.2562 + *
3.2563 + * +----------------------------------------------------+
3.2564 + * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) |
3.2565 + * +----------------------------------------------------+
3.2566 + * ^ ^ ^
3.2567 + * | | |
3.2568 + * left p k
3.2569 + *
3.2570 + * Invariants:
3.2571 + *
3.2572 + * all in (*, left) < 0.0
3.2573 + * all in [left, p) == -0.0
3.2574 + * all in [p, k) == 0.0
3.2575 + * all in [k, right] >= 0.0
3.2576 + *
3.2577 + * Pointer k is the first index of ?-part.
3.2578 + */
3.2579 + for (int k = left, p = left - 1; ++k <= right; ) {
3.2580 + double ak = a[k];
3.2581 + if (ak != 0.0d) {
3.2582 + break;
3.2583 + }
3.2584 + if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
3.2585 + a[k] = 0.0d;
3.2586 + a[++p] = -0.0d;
3.2587 + }
3.2588 + }
3.2589 + }
3.2590 +
3.2591 + /**
3.2592 + * Sorts the specified range of the array.
3.2593 + *
3.2594 + * @param a the array to be sorted
3.2595 + * @param left the index of the first element, inclusive, to be sorted
3.2596 + * @param right the index of the last element, inclusive, to be sorted
3.2597 + */
3.2598 + private static void doSort(double[] a, int left, int right) {
3.2599 + // Use Quicksort on small arrays
3.2600 + if (right - left < QUICKSORT_THRESHOLD) {
3.2601 + sort(a, left, right, true);
3.2602 + return;
3.2603 + }
3.2604 +
3.2605 + /*
3.2606 + * Index run[i] is the start of i-th run
3.2607 + * (ascending or descending sequence).
3.2608 + */
3.2609 + int[] run = new int[MAX_RUN_COUNT + 1];
3.2610 + int count = 0; run[0] = left;
3.2611 +
3.2612 + // Check if the array is nearly sorted
3.2613 + for (int k = left; k < right; run[count] = k) {
3.2614 + if (a[k] < a[k + 1]) { // ascending
3.2615 + while (++k <= right && a[k - 1] <= a[k]);
3.2616 + } else if (a[k] > a[k + 1]) { // descending
3.2617 + while (++k <= right && a[k - 1] >= a[k]);
3.2618 + for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
3.2619 + double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
3.2620 + }
3.2621 + } else { // equal
3.2622 + for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
3.2623 + if (--m == 0) {
3.2624 + sort(a, left, right, true);
3.2625 + return;
3.2626 + }
3.2627 + }
3.2628 + }
3.2629 +
3.2630 + /*
3.2631 + * The array is not highly structured,
3.2632 + * use Quicksort instead of merge sort.
3.2633 + */
3.2634 + if (++count == MAX_RUN_COUNT) {
3.2635 + sort(a, left, right, true);
3.2636 + return;
3.2637 + }
3.2638 + }
3.2639 +
3.2640 + // Check special cases
3.2641 + if (run[count] == right++) { // The last run contains one element
3.2642 + run[++count] = right;
3.2643 + } else if (count == 1) { // The array is already sorted
3.2644 + return;
3.2645 + }
3.2646 +
3.2647 + /*
3.2648 + * Create temporary array, which is used for merging.
3.2649 + * Implementation note: variable "right" is increased by 1.
3.2650 + */
3.2651 + double[] b; byte odd = 0;
3.2652 + for (int n = 1; (n <<= 1) < count; odd ^= 1);
3.2653 +
3.2654 + if (odd == 0) {
3.2655 + b = a; a = new double[b.length];
3.2656 + for (int i = left - 1; ++i < right; a[i] = b[i]);
3.2657 + } else {
3.2658 + b = new double[a.length];
3.2659 + }
3.2660 +
3.2661 + // Merging
3.2662 + for (int last; count > 1; count = last) {
3.2663 + for (int k = (last = 0) + 2; k <= count; k += 2) {
3.2664 + int hi = run[k], mi = run[k - 1];
3.2665 + for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
3.2666 + if (q >= hi || p < mi && a[p] <= a[q]) {
3.2667 + b[i] = a[p++];
3.2668 + } else {
3.2669 + b[i] = a[q++];
3.2670 + }
3.2671 + }
3.2672 + run[++last] = hi;
3.2673 + }
3.2674 + if ((count & 1) != 0) {
3.2675 + for (int i = right, lo = run[count - 1]; --i >= lo;
3.2676 + b[i] = a[i]
3.2677 + );
3.2678 + run[++last] = right;
3.2679 + }
3.2680 + double[] t = a; a = b; b = t;
3.2681 + }
3.2682 + }
3.2683 +
3.2684 + /**
3.2685 + * Sorts the specified range of the array by Dual-Pivot Quicksort.
3.2686 + *
3.2687 + * @param a the array to be sorted
3.2688 + * @param left the index of the first element, inclusive, to be sorted
3.2689 + * @param right the index of the last element, inclusive, to be sorted
3.2690 + * @param leftmost indicates if this part is the leftmost in the range
3.2691 + */
3.2692 + private static void sort(double[] a, int left, int right, boolean leftmost) {
3.2693 + int length = right - left + 1;
3.2694 +
3.2695 + // Use insertion sort on tiny arrays
3.2696 + if (length < INSERTION_SORT_THRESHOLD) {
3.2697 + if (leftmost) {
3.2698 + /*
3.2699 + * Traditional (without sentinel) insertion sort,
3.2700 + * optimized for server VM, is used in case of
3.2701 + * the leftmost part.
3.2702 + */
3.2703 + for (int i = left, j = i; i < right; j = ++i) {
3.2704 + double ai = a[i + 1];
3.2705 + while (ai < a[j]) {
3.2706 + a[j + 1] = a[j];
3.2707 + if (j-- == left) {
3.2708 + break;
3.2709 + }
3.2710 + }
3.2711 + a[j + 1] = ai;
3.2712 + }
3.2713 + } else {
3.2714 + /*
3.2715 + * Skip the longest ascending sequence.
3.2716 + */
3.2717 + do {
3.2718 + if (left >= right) {
3.2719 + return;
3.2720 + }
3.2721 + } while (a[++left] >= a[left - 1]);
3.2722 +
3.2723 + /*
3.2724 + * Every element from adjoining part plays the role
3.2725 + * of sentinel, therefore this allows us to avoid the
3.2726 + * left range check on each iteration. Moreover, we use
3.2727 + * the more optimized algorithm, so called pair insertion
3.2728 + * sort, which is faster (in the context of Quicksort)
3.2729 + * than traditional implementation of insertion sort.
3.2730 + */
3.2731 + for (int k = left; ++left <= right; k = ++left) {
3.2732 + double a1 = a[k], a2 = a[left];
3.2733 +
3.2734 + if (a1 < a2) {
3.2735 + a2 = a1; a1 = a[left];
3.2736 + }
3.2737 + while (a1 < a[--k]) {
3.2738 + a[k + 2] = a[k];
3.2739 + }
3.2740 + a[++k + 1] = a1;
3.2741 +
3.2742 + while (a2 < a[--k]) {
3.2743 + a[k + 1] = a[k];
3.2744 + }
3.2745 + a[k + 1] = a2;
3.2746 + }
3.2747 + double last = a[right];
3.2748 +
3.2749 + while (last < a[--right]) {
3.2750 + a[right + 1] = a[right];
3.2751 + }
3.2752 + a[right + 1] = last;
3.2753 + }
3.2754 + return;
3.2755 + }
3.2756 +
3.2757 + // Inexpensive approximation of length / 7
3.2758 + int seventh = (length >> 3) + (length >> 6) + 1;
3.2759 +
3.2760 + /*
3.2761 + * Sort five evenly spaced elements around (and including) the
3.2762 + * center element in the range. These elements will be used for
3.2763 + * pivot selection as described below. The choice for spacing
3.2764 + * these elements was empirically determined to work well on
3.2765 + * a wide variety of inputs.
3.2766 + */
3.2767 + int e3 = (left + right) >>> 1; // The midpoint
3.2768 + int e2 = e3 - seventh;
3.2769 + int e1 = e2 - seventh;
3.2770 + int e4 = e3 + seventh;
3.2771 + int e5 = e4 + seventh;
3.2772 +
3.2773 + // Sort these elements using insertion sort
3.2774 + if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
3.2775 +
3.2776 + if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
3.2777 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2778 + }
3.2779 + if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
3.2780 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.2781 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2782 + }
3.2783 + }
3.2784 + if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
3.2785 + if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
3.2786 + if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
3.2787 + if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
3.2788 + }
3.2789 + }
3.2790 + }
3.2791 +
3.2792 + // Pointers
3.2793 + int less = left; // The index of the first element of center part
3.2794 + int great = right; // The index before the first element of right part
3.2795 +
3.2796 + if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
3.2797 + /*
3.2798 + * Use the second and fourth of the five sorted elements as pivots.
3.2799 + * These values are inexpensive approximations of the first and
3.2800 + * second terciles of the array. Note that pivot1 <= pivot2.
3.2801 + */
3.2802 + double pivot1 = a[e2];
3.2803 + double pivot2 = a[e4];
3.2804 +
3.2805 + /*
3.2806 + * The first and the last elements to be sorted are moved to the
3.2807 + * locations formerly occupied by the pivots. When partitioning
3.2808 + * is complete, the pivots are swapped back into their final
3.2809 + * positions, and excluded from subsequent sorting.
3.2810 + */
3.2811 + a[e2] = a[left];
3.2812 + a[e4] = a[right];
3.2813 +
3.2814 + /*
3.2815 + * Skip elements, which are less or greater than pivot values.
3.2816 + */
3.2817 + while (a[++less] < pivot1);
3.2818 + while (a[--great] > pivot2);
3.2819 +
3.2820 + /*
3.2821 + * Partitioning:
3.2822 + *
3.2823 + * left part center part right part
3.2824 + * +--------------------------------------------------------------+
3.2825 + * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
3.2826 + * +--------------------------------------------------------------+
3.2827 + * ^ ^ ^
3.2828 + * | | |
3.2829 + * less k great
3.2830 + *
3.2831 + * Invariants:
3.2832 + *
3.2833 + * all in (left, less) < pivot1
3.2834 + * pivot1 <= all in [less, k) <= pivot2
3.2835 + * all in (great, right) > pivot2
3.2836 + *
3.2837 + * Pointer k is the first index of ?-part.
3.2838 + */
3.2839 + outer:
3.2840 + for (int k = less - 1; ++k <= great; ) {
3.2841 + double ak = a[k];
3.2842 + if (ak < pivot1) { // Move a[k] to left part
3.2843 + a[k] = a[less];
3.2844 + /*
3.2845 + * Here and below we use "a[i] = b; i++;" instead
3.2846 + * of "a[i++] = b;" due to performance issue.
3.2847 + */
3.2848 + a[less] = ak;
3.2849 + ++less;
3.2850 + } else if (ak > pivot2) { // Move a[k] to right part
3.2851 + while (a[great] > pivot2) {
3.2852 + if (great-- == k) {
3.2853 + break outer;
3.2854 + }
3.2855 + }
3.2856 + if (a[great] < pivot1) { // a[great] <= pivot2
3.2857 + a[k] = a[less];
3.2858 + a[less] = a[great];
3.2859 + ++less;
3.2860 + } else { // pivot1 <= a[great] <= pivot2
3.2861 + a[k] = a[great];
3.2862 + }
3.2863 + /*
3.2864 + * Here and below we use "a[i] = b; i--;" instead
3.2865 + * of "a[i--] = b;" due to performance issue.
3.2866 + */
3.2867 + a[great] = ak;
3.2868 + --great;
3.2869 + }
3.2870 + }
3.2871 +
3.2872 + // Swap pivots into their final positions
3.2873 + a[left] = a[less - 1]; a[less - 1] = pivot1;
3.2874 + a[right] = a[great + 1]; a[great + 1] = pivot2;
3.2875 +
3.2876 + // Sort left and right parts recursively, excluding known pivots
3.2877 + sort(a, left, less - 2, leftmost);
3.2878 + sort(a, great + 2, right, false);
3.2879 +
3.2880 + /*
3.2881 + * If center part is too large (comprises > 4/7 of the array),
3.2882 + * swap internal pivot values to ends.
3.2883 + */
3.2884 + if (less < e1 && e5 < great) {
3.2885 + /*
3.2886 + * Skip elements, which are equal to pivot values.
3.2887 + */
3.2888 + while (a[less] == pivot1) {
3.2889 + ++less;
3.2890 + }
3.2891 +
3.2892 + while (a[great] == pivot2) {
3.2893 + --great;
3.2894 + }
3.2895 +
3.2896 + /*
3.2897 + * Partitioning:
3.2898 + *
3.2899 + * left part center part right part
3.2900 + * +----------------------------------------------------------+
3.2901 + * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
3.2902 + * +----------------------------------------------------------+
3.2903 + * ^ ^ ^
3.2904 + * | | |
3.2905 + * less k great
3.2906 + *
3.2907 + * Invariants:
3.2908 + *
3.2909 + * all in (*, less) == pivot1
3.2910 + * pivot1 < all in [less, k) < pivot2
3.2911 + * all in (great, *) == pivot2
3.2912 + *
3.2913 + * Pointer k is the first index of ?-part.
3.2914 + */
3.2915 + outer:
3.2916 + for (int k = less - 1; ++k <= great; ) {
3.2917 + double ak = a[k];
3.2918 + if (ak == pivot1) { // Move a[k] to left part
3.2919 + a[k] = a[less];
3.2920 + a[less] = ak;
3.2921 + ++less;
3.2922 + } else if (ak == pivot2) { // Move a[k] to right part
3.2923 + while (a[great] == pivot2) {
3.2924 + if (great-- == k) {
3.2925 + break outer;
3.2926 + }
3.2927 + }
3.2928 + if (a[great] == pivot1) { // a[great] < pivot2
3.2929 + a[k] = a[less];
3.2930 + /*
3.2931 + * Even though a[great] equals to pivot1, the
3.2932 + * assignment a[less] = pivot1 may be incorrect,
3.2933 + * if a[great] and pivot1 are floating-point zeros
3.2934 + * of different signs. Therefore in float and
3.2935 + * double sorting methods we have to use more
3.2936 + * accurate assignment a[less] = a[great].
3.2937 + */
3.2938 + a[less] = a[great];
3.2939 + ++less;
3.2940 + } else { // pivot1 < a[great] < pivot2
3.2941 + a[k] = a[great];
3.2942 + }
3.2943 + a[great] = ak;
3.2944 + --great;
3.2945 + }
3.2946 + }
3.2947 + }
3.2948 +
3.2949 + // Sort center part recursively
3.2950 + sort(a, less, great, false);
3.2951 +
3.2952 + } else { // Partitioning with one pivot
3.2953 + /*
3.2954 + * Use the third of the five sorted elements as pivot.
3.2955 + * This value is inexpensive approximation of the median.
3.2956 + */
3.2957 + double pivot = a[e3];
3.2958 +
3.2959 + /*
3.2960 + * Partitioning degenerates to the traditional 3-way
3.2961 + * (or "Dutch National Flag") schema:
3.2962 + *
3.2963 + * left part center part right part
3.2964 + * +-------------------------------------------------+
3.2965 + * | < pivot | == pivot | ? | > pivot |
3.2966 + * +-------------------------------------------------+
3.2967 + * ^ ^ ^
3.2968 + * | | |
3.2969 + * less k great
3.2970 + *
3.2971 + * Invariants:
3.2972 + *
3.2973 + * all in (left, less) < pivot
3.2974 + * all in [less, k) == pivot
3.2975 + * all in (great, right) > pivot
3.2976 + *
3.2977 + * Pointer k is the first index of ?-part.
3.2978 + */
3.2979 + for (int k = less; k <= great; ++k) {
3.2980 + if (a[k] == pivot) {
3.2981 + continue;
3.2982 + }
3.2983 + double ak = a[k];
3.2984 + if (ak < pivot) { // Move a[k] to left part
3.2985 + a[k] = a[less];
3.2986 + a[less] = ak;
3.2987 + ++less;
3.2988 + } else { // a[k] > pivot - Move a[k] to right part
3.2989 + while (a[great] > pivot) {
3.2990 + --great;
3.2991 + }
3.2992 + if (a[great] < pivot) { // a[great] <= pivot
3.2993 + a[k] = a[less];
3.2994 + a[less] = a[great];
3.2995 + ++less;
3.2996 + } else { // a[great] == pivot
3.2997 + /*
3.2998 + * Even though a[great] equals to pivot, the
3.2999 + * assignment a[k] = pivot may be incorrect,
3.3000 + * if a[great] and pivot are floating-point
3.3001 + * zeros of different signs. Therefore in float
3.3002 + * and double sorting methods we have to use
3.3003 + * more accurate assignment a[k] = a[great].
3.3004 + */
3.3005 + a[k] = a[great];
3.3006 + }
3.3007 + a[great] = ak;
3.3008 + --great;
3.3009 + }
3.3010 + }
3.3011 +
3.3012 + /*
3.3013 + * Sort left and right parts recursively.
3.3014 + * All elements from center part are equal
3.3015 + * and, therefore, already sorted.
3.3016 + */
3.3017 + sort(a, left, less - 1, leftmost);
3.3018 + sort(a, great + 1, right, false);
3.3019 + }
3.3020 + }
3.3021 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/emul/compact/src/main/java/java/util/TimSort.java Wed Jan 23 23:19:47 2013 +0100
4.3 @@ -0,0 +1,928 @@
4.4 +/*
4.5 + * Copyright 2009 Google Inc. All Rights Reserved.
4.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4.7 + *
4.8 + * This code is free software; you can redistribute it and/or modify it
4.9 + * under the terms of the GNU General Public License version 2 only, as
4.10 + * published by the Free Software Foundation. Oracle designates this
4.11 + * particular file as subject to the "Classpath" exception as provided
4.12 + * by Oracle in the LICENSE file that accompanied this code.
4.13 + *
4.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
4.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
4.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
4.17 + * version 2 for more details (a copy is included in the LICENSE file that
4.18 + * accompanied this code).
4.19 + *
4.20 + * You should have received a copy of the GNU General Public License version
4.21 + * 2 along with this work; if not, write to the Free Software Foundation,
4.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
4.23 + *
4.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
4.25 + * or visit www.oracle.com if you need additional information or have any
4.26 + * questions.
4.27 + */
4.28 +
4.29 +package java.util;
4.30 +
4.31 +/**
4.32 + * A stable, adaptive, iterative mergesort that requires far fewer than
4.33 + * n lg(n) comparisons when running on partially sorted arrays, while
4.34 + * offering performance comparable to a traditional mergesort when run
4.35 + * on random arrays. Like all proper mergesorts, this sort is stable and
4.36 + * runs O(n log n) time (worst case). In the worst case, this sort requires
4.37 + * temporary storage space for n/2 object references; in the best case,
4.38 + * it requires only a small constant amount of space.
4.39 + *
4.40 + * This implementation was adapted from Tim Peters's list sort for
4.41 + * Python, which is described in detail here:
4.42 + *
4.43 + * http://svn.python.org/projects/python/trunk/Objects/listsort.txt
4.44 + *
4.45 + * Tim's C code may be found here:
4.46 + *
4.47 + * http://svn.python.org/projects/python/trunk/Objects/listobject.c
4.48 + *
4.49 + * The underlying techniques are described in this paper (and may have
4.50 + * even earlier origins):
4.51 + *
4.52 + * "Optimistic Sorting and Information Theoretic Complexity"
4.53 + * Peter McIlroy
4.54 + * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
4.55 + * pp 467-474, Austin, Texas, 25-27 January 1993.
4.56 + *
4.57 + * While the API to this class consists solely of static methods, it is
4.58 + * (privately) instantiable; a TimSort instance holds the state of an ongoing
4.59 + * sort, assuming the input array is large enough to warrant the full-blown
4.60 + * TimSort. Small arrays are sorted in place, using a binary insertion sort.
4.61 + *
4.62 + * @author Josh Bloch
4.63 + */
4.64 +class TimSort<T> {
4.65 + /**
4.66 + * This is the minimum sized sequence that will be merged. Shorter
4.67 + * sequences will be lengthened by calling binarySort. If the entire
4.68 + * array is less than this length, no merges will be performed.
4.69 + *
4.70 + * This constant should be a power of two. It was 64 in Tim Peter's C
4.71 + * implementation, but 32 was empirically determined to work better in
4.72 + * this implementation. In the unlikely event that you set this constant
4.73 + * to be a number that's not a power of two, you'll need to change the
4.74 + * {@link #minRunLength} computation.
4.75 + *
4.76 + * If you decrease this constant, you must change the stackLen
4.77 + * computation in the TimSort constructor, or you risk an
4.78 + * ArrayOutOfBounds exception. See listsort.txt for a discussion
4.79 + * of the minimum stack length required as a function of the length
4.80 + * of the array being sorted and the minimum merge sequence length.
4.81 + */
4.82 + private static final int MIN_MERGE = 32;
4.83 +
4.84 + /**
4.85 + * The array being sorted.
4.86 + */
4.87 + private final T[] a;
4.88 +
4.89 + /**
4.90 + * The comparator for this sort.
4.91 + */
4.92 + private final Comparator<? super T> c;
4.93 +
4.94 + /**
4.95 + * When we get into galloping mode, we stay there until both runs win less
4.96 + * often than MIN_GALLOP consecutive times.
4.97 + */
4.98 + private static final int MIN_GALLOP = 7;
4.99 +
4.100 + /**
4.101 + * This controls when we get *into* galloping mode. It is initialized
4.102 + * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
4.103 + * random data, and lower for highly structured data.
4.104 + */
4.105 + private int minGallop = MIN_GALLOP;
4.106 +
4.107 + /**
4.108 + * Maximum initial size of tmp array, which is used for merging. The array
4.109 + * can grow to accommodate demand.
4.110 + *
4.111 + * Unlike Tim's original C version, we do not allocate this much storage
4.112 + * when sorting smaller arrays. This change was required for performance.
4.113 + */
4.114 + private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
4.115 +
4.116 + /**
4.117 + * Temp storage for merges.
4.118 + */
4.119 + private T[] tmp; // Actual runtime type will be Object[], regardless of T
4.120 +
4.121 + /**
4.122 + * A stack of pending runs yet to be merged. Run i starts at
4.123 + * address base[i] and extends for len[i] elements. It's always
4.124 + * true (so long as the indices are in bounds) that:
4.125 + *
4.126 + * runBase[i] + runLen[i] == runBase[i + 1]
4.127 + *
4.128 + * so we could cut the storage for this, but it's a minor amount,
4.129 + * and keeping all the info explicit simplifies the code.
4.130 + */
4.131 + private int stackSize = 0; // Number of pending runs on stack
4.132 + private final int[] runBase;
4.133 + private final int[] runLen;
4.134 +
4.135 + /**
4.136 + * Creates a TimSort instance to maintain the state of an ongoing sort.
4.137 + *
4.138 + * @param a the array to be sorted
4.139 + * @param c the comparator to determine the order of the sort
4.140 + */
4.141 + private TimSort(T[] a, Comparator<? super T> c) {
4.142 + this.a = a;
4.143 + this.c = c;
4.144 +
4.145 + // Allocate temp storage (which may be increased later if necessary)
4.146 + int len = a.length;
4.147 + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
4.148 + T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
4.149 + len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
4.150 + tmp = newArray;
4.151 +
4.152 + /*
4.153 + * Allocate runs-to-be-merged stack (which cannot be expanded). The
4.154 + * stack length requirements are described in listsort.txt. The C
4.155 + * version always uses the same stack length (85), but this was
4.156 + * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
4.157 + * 100 elements) in Java. Therefore, we use smaller (but sufficiently
4.158 + * large) stack lengths for smaller arrays. The "magic numbers" in the
4.159 + * computation below must be changed if MIN_MERGE is decreased. See
4.160 + * the MIN_MERGE declaration above for more information.
4.161 + */
4.162 + int stackLen = (len < 120 ? 5 :
4.163 + len < 1542 ? 10 :
4.164 + len < 119151 ? 19 : 40);
4.165 + runBase = new int[stackLen];
4.166 + runLen = new int[stackLen];
4.167 + }
4.168 +
4.169 + /*
4.170 + * The next two methods (which are package private and static) constitute
4.171 + * the entire API of this class. Each of these methods obeys the contract
4.172 + * of the public method with the same signature in java.util.Arrays.
4.173 + */
4.174 +
4.175 + static <T> void sort(T[] a, Comparator<? super T> c) {
4.176 + sort(a, 0, a.length, c);
4.177 + }
4.178 +
4.179 + static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
4.180 + if (c == null) {
4.181 + Arrays.sort(a, lo, hi);
4.182 + return;
4.183 + }
4.184 +
4.185 + rangeCheck(a.length, lo, hi);
4.186 + int nRemaining = hi - lo;
4.187 + if (nRemaining < 2)
4.188 + return; // Arrays of size 0 and 1 are always sorted
4.189 +
4.190 + // If array is small, do a "mini-TimSort" with no merges
4.191 + if (nRemaining < MIN_MERGE) {
4.192 + int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
4.193 + binarySort(a, lo, hi, lo + initRunLen, c);
4.194 + return;
4.195 + }
4.196 +
4.197 + /**
4.198 + * March over the array once, left to right, finding natural runs,
4.199 + * extending short natural runs to minRun elements, and merging runs
4.200 + * to maintain stack invariant.
4.201 + */
4.202 + TimSort<T> ts = new TimSort<>(a, c);
4.203 + int minRun = minRunLength(nRemaining);
4.204 + do {
4.205 + // Identify next run
4.206 + int runLen = countRunAndMakeAscending(a, lo, hi, c);
4.207 +
4.208 + // If run is short, extend to min(minRun, nRemaining)
4.209 + if (runLen < minRun) {
4.210 + int force = nRemaining <= minRun ? nRemaining : minRun;
4.211 + binarySort(a, lo, lo + force, lo + runLen, c);
4.212 + runLen = force;
4.213 + }
4.214 +
4.215 + // Push run onto pending-run stack, and maybe merge
4.216 + ts.pushRun(lo, runLen);
4.217 + ts.mergeCollapse();
4.218 +
4.219 + // Advance to find next run
4.220 + lo += runLen;
4.221 + nRemaining -= runLen;
4.222 + } while (nRemaining != 0);
4.223 +
4.224 + // Merge all remaining runs to complete sort
4.225 + assert lo == hi;
4.226 + ts.mergeForceCollapse();
4.227 + assert ts.stackSize == 1;
4.228 + }
4.229 +
4.230 + /**
4.231 + * Sorts the specified portion of the specified array using a binary
4.232 + * insertion sort. This is the best method for sorting small numbers
4.233 + * of elements. It requires O(n log n) compares, but O(n^2) data
4.234 + * movement (worst case).
4.235 + *
4.236 + * If the initial part of the specified range is already sorted,
4.237 + * this method can take advantage of it: the method assumes that the
4.238 + * elements from index {@code lo}, inclusive, to {@code start},
4.239 + * exclusive are already sorted.
4.240 + *
4.241 + * @param a the array in which a range is to be sorted
4.242 + * @param lo the index of the first element in the range to be sorted
4.243 + * @param hi the index after the last element in the range to be sorted
4.244 + * @param start the index of the first element in the range that is
4.245 + * not already known to be sorted ({@code lo <= start <= hi})
4.246 + * @param c comparator to used for the sort
4.247 + */
4.248 + @SuppressWarnings("fallthrough")
4.249 + private static <T> void binarySort(T[] a, int lo, int hi, int start,
4.250 + Comparator<? super T> c) {
4.251 + assert lo <= start && start <= hi;
4.252 + if (start == lo)
4.253 + start++;
4.254 + for ( ; start < hi; start++) {
4.255 + T pivot = a[start];
4.256 +
4.257 + // Set left (and right) to the index where a[start] (pivot) belongs
4.258 + int left = lo;
4.259 + int right = start;
4.260 + assert left <= right;
4.261 + /*
4.262 + * Invariants:
4.263 + * pivot >= all in [lo, left).
4.264 + * pivot < all in [right, start).
4.265 + */
4.266 + while (left < right) {
4.267 + int mid = (left + right) >>> 1;
4.268 + if (c.compare(pivot, a[mid]) < 0)
4.269 + right = mid;
4.270 + else
4.271 + left = mid + 1;
4.272 + }
4.273 + assert left == right;
4.274 +
4.275 + /*
4.276 + * The invariants still hold: pivot >= all in [lo, left) and
4.277 + * pivot < all in [left, start), so pivot belongs at left. Note
4.278 + * that if there are elements equal to pivot, left points to the
4.279 + * first slot after them -- that's why this sort is stable.
4.280 + * Slide elements over to make room for pivot.
4.281 + */
4.282 + int n = start - left; // The number of elements to move
4.283 + // Switch is just an optimization for arraycopy in default case
4.284 + switch (n) {
4.285 + case 2: a[left + 2] = a[left + 1];
4.286 + case 1: a[left + 1] = a[left];
4.287 + break;
4.288 + default: System.arraycopy(a, left, a, left + 1, n);
4.289 + }
4.290 + a[left] = pivot;
4.291 + }
4.292 + }
4.293 +
4.294 + /**
4.295 + * Returns the length of the run beginning at the specified position in
4.296 + * the specified array and reverses the run if it is descending (ensuring
4.297 + * that the run will always be ascending when the method returns).
4.298 + *
4.299 + * A run is the longest ascending sequence with:
4.300 + *
4.301 + * a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
4.302 + *
4.303 + * or the longest descending sequence with:
4.304 + *
4.305 + * a[lo] > a[lo + 1] > a[lo + 2] > ...
4.306 + *
4.307 + * For its intended use in a stable mergesort, the strictness of the
4.308 + * definition of "descending" is needed so that the call can safely
4.309 + * reverse a descending sequence without violating stability.
4.310 + *
4.311 + * @param a the array in which a run is to be counted and possibly reversed
4.312 + * @param lo index of the first element in the run
4.313 + * @param hi index after the last element that may be contained in the run.
4.314 + It is required that {@code lo < hi}.
4.315 + * @param c the comparator to used for the sort
4.316 + * @return the length of the run beginning at the specified position in
4.317 + * the specified array
4.318 + */
4.319 + private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
4.320 + Comparator<? super T> c) {
4.321 + assert lo < hi;
4.322 + int runHi = lo + 1;
4.323 + if (runHi == hi)
4.324 + return 1;
4.325 +
4.326 + // Find end of run, and reverse range if descending
4.327 + if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
4.328 + while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
4.329 + runHi++;
4.330 + reverseRange(a, lo, runHi);
4.331 + } else { // Ascending
4.332 + while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
4.333 + runHi++;
4.334 + }
4.335 +
4.336 + return runHi - lo;
4.337 + }
4.338 +
4.339 + /**
4.340 + * Reverse the specified range of the specified array.
4.341 + *
4.342 + * @param a the array in which a range is to be reversed
4.343 + * @param lo the index of the first element in the range to be reversed
4.344 + * @param hi the index after the last element in the range to be reversed
4.345 + */
4.346 + private static void reverseRange(Object[] a, int lo, int hi) {
4.347 + hi--;
4.348 + while (lo < hi) {
4.349 + Object t = a[lo];
4.350 + a[lo++] = a[hi];
4.351 + a[hi--] = t;
4.352 + }
4.353 + }
4.354 +
4.355 + /**
4.356 + * Returns the minimum acceptable run length for an array of the specified
4.357 + * length. Natural runs shorter than this will be extended with
4.358 + * {@link #binarySort}.
4.359 + *
4.360 + * Roughly speaking, the computation is:
4.361 + *
4.362 + * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
4.363 + * Else if n is an exact power of 2, return MIN_MERGE/2.
4.364 + * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
4.365 + * is close to, but strictly less than, an exact power of 2.
4.366 + *
4.367 + * For the rationale, see listsort.txt.
4.368 + *
4.369 + * @param n the length of the array to be sorted
4.370 + * @return the length of the minimum run to be merged
4.371 + */
4.372 + private static int minRunLength(int n) {
4.373 + assert n >= 0;
4.374 + int r = 0; // Becomes 1 if any 1 bits are shifted off
4.375 + while (n >= MIN_MERGE) {
4.376 + r |= (n & 1);
4.377 + n >>= 1;
4.378 + }
4.379 + return n + r;
4.380 + }
4.381 +
4.382 + /**
4.383 + * Pushes the specified run onto the pending-run stack.
4.384 + *
4.385 + * @param runBase index of the first element in the run
4.386 + * @param runLen the number of elements in the run
4.387 + */
4.388 + private void pushRun(int runBase, int runLen) {
4.389 + this.runBase[stackSize] = runBase;
4.390 + this.runLen[stackSize] = runLen;
4.391 + stackSize++;
4.392 + }
4.393 +
4.394 + /**
4.395 + * Examines the stack of runs waiting to be merged and merges adjacent runs
4.396 + * until the stack invariants are reestablished:
4.397 + *
4.398 + * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
4.399 + * 2. runLen[i - 2] > runLen[i - 1]
4.400 + *
4.401 + * This method is called each time a new run is pushed onto the stack,
4.402 + * so the invariants are guaranteed to hold for i < stackSize upon
4.403 + * entry to the method.
4.404 + */
4.405 + private void mergeCollapse() {
4.406 + while (stackSize > 1) {
4.407 + int n = stackSize - 2;
4.408 + if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
4.409 + if (runLen[n - 1] < runLen[n + 1])
4.410 + n--;
4.411 + mergeAt(n);
4.412 + } else if (runLen[n] <= runLen[n + 1]) {
4.413 + mergeAt(n);
4.414 + } else {
4.415 + break; // Invariant is established
4.416 + }
4.417 + }
4.418 + }
4.419 +
4.420 + /**
4.421 + * Merges all runs on the stack until only one remains. This method is
4.422 + * called once, to complete the sort.
4.423 + */
4.424 + private void mergeForceCollapse() {
4.425 + while (stackSize > 1) {
4.426 + int n = stackSize - 2;
4.427 + if (n > 0 && runLen[n - 1] < runLen[n + 1])
4.428 + n--;
4.429 + mergeAt(n);
4.430 + }
4.431 + }
4.432 +
4.433 + /**
4.434 + * Merges the two runs at stack indices i and i+1. Run i must be
4.435 + * the penultimate or antepenultimate run on the stack. In other words,
4.436 + * i must be equal to stackSize-2 or stackSize-3.
4.437 + *
4.438 + * @param i stack index of the first of the two runs to merge
4.439 + */
4.440 + private void mergeAt(int i) {
4.441 + assert stackSize >= 2;
4.442 + assert i >= 0;
4.443 + assert i == stackSize - 2 || i == stackSize - 3;
4.444 +
4.445 + int base1 = runBase[i];
4.446 + int len1 = runLen[i];
4.447 + int base2 = runBase[i + 1];
4.448 + int len2 = runLen[i + 1];
4.449 + assert len1 > 0 && len2 > 0;
4.450 + assert base1 + len1 == base2;
4.451 +
4.452 + /*
4.453 + * Record the length of the combined runs; if i is the 3rd-last
4.454 + * run now, also slide over the last run (which isn't involved
4.455 + * in this merge). The current run (i+1) goes away in any case.
4.456 + */
4.457 + runLen[i] = len1 + len2;
4.458 + if (i == stackSize - 3) {
4.459 + runBase[i + 1] = runBase[i + 2];
4.460 + runLen[i + 1] = runLen[i + 2];
4.461 + }
4.462 + stackSize--;
4.463 +
4.464 + /*
4.465 + * Find where the first element of run2 goes in run1. Prior elements
4.466 + * in run1 can be ignored (because they're already in place).
4.467 + */
4.468 + int k = gallopRight(a[base2], a, base1, len1, 0, c);
4.469 + assert k >= 0;
4.470 + base1 += k;
4.471 + len1 -= k;
4.472 + if (len1 == 0)
4.473 + return;
4.474 +
4.475 + /*
4.476 + * Find where the last element of run1 goes in run2. Subsequent elements
4.477 + * in run2 can be ignored (because they're already in place).
4.478 + */
4.479 + len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
4.480 + assert len2 >= 0;
4.481 + if (len2 == 0)
4.482 + return;
4.483 +
4.484 + // Merge remaining runs, using tmp array with min(len1, len2) elements
4.485 + if (len1 <= len2)
4.486 + mergeLo(base1, len1, base2, len2);
4.487 + else
4.488 + mergeHi(base1, len1, base2, len2);
4.489 + }
4.490 +
4.491 + /**
4.492 + * Locates the position at which to insert the specified key into the
4.493 + * specified sorted range; if the range contains an element equal to key,
4.494 + * returns the index of the leftmost equal element.
4.495 + *
4.496 + * @param key the key whose insertion point to search for
4.497 + * @param a the array in which to search
4.498 + * @param base the index of the first element in the range
4.499 + * @param len the length of the range; must be > 0
4.500 + * @param hint the index at which to begin the search, 0 <= hint < n.
4.501 + * The closer hint is to the result, the faster this method will run.
4.502 + * @param c the comparator used to order the range, and to search
4.503 + * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
4.504 + * pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
4.505 + * In other words, key belongs at index b + k; or in other words,
4.506 + * the first k elements of a should precede key, and the last n - k
4.507 + * should follow it.
4.508 + */
4.509 + private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
4.510 + Comparator<? super T> c) {
4.511 + assert len > 0 && hint >= 0 && hint < len;
4.512 + int lastOfs = 0;
4.513 + int ofs = 1;
4.514 + if (c.compare(key, a[base + hint]) > 0) {
4.515 + // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
4.516 + int maxOfs = len - hint;
4.517 + while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) {
4.518 + lastOfs = ofs;
4.519 + ofs = (ofs << 1) + 1;
4.520 + if (ofs <= 0) // int overflow
4.521 + ofs = maxOfs;
4.522 + }
4.523 + if (ofs > maxOfs)
4.524 + ofs = maxOfs;
4.525 +
4.526 + // Make offsets relative to base
4.527 + lastOfs += hint;
4.528 + ofs += hint;
4.529 + } else { // key <= a[base + hint]
4.530 + // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
4.531 + final int maxOfs = hint + 1;
4.532 + while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) {
4.533 + lastOfs = ofs;
4.534 + ofs = (ofs << 1) + 1;
4.535 + if (ofs <= 0) // int overflow
4.536 + ofs = maxOfs;
4.537 + }
4.538 + if (ofs > maxOfs)
4.539 + ofs = maxOfs;
4.540 +
4.541 + // Make offsets relative to base
4.542 + int tmp = lastOfs;
4.543 + lastOfs = hint - ofs;
4.544 + ofs = hint - tmp;
4.545 + }
4.546 + assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
4.547 +
4.548 + /*
4.549 + * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
4.550 + * to the right of lastOfs but no farther right than ofs. Do a binary
4.551 + * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
4.552 + */
4.553 + lastOfs++;
4.554 + while (lastOfs < ofs) {
4.555 + int m = lastOfs + ((ofs - lastOfs) >>> 1);
4.556 +
4.557 + if (c.compare(key, a[base + m]) > 0)
4.558 + lastOfs = m + 1; // a[base + m] < key
4.559 + else
4.560 + ofs = m; // key <= a[base + m]
4.561 + }
4.562 + assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs]
4.563 + return ofs;
4.564 + }
4.565 +
4.566 + /**
4.567 + * Like gallopLeft, except that if the range contains an element equal to
4.568 + * key, gallopRight returns the index after the rightmost equal element.
4.569 + *
4.570 + * @param key the key whose insertion point to search for
4.571 + * @param a the array in which to search
4.572 + * @param base the index of the first element in the range
4.573 + * @param len the length of the range; must be > 0
4.574 + * @param hint the index at which to begin the search, 0 <= hint < n.
4.575 + * The closer hint is to the result, the faster this method will run.
4.576 + * @param c the comparator used to order the range, and to search
4.577 + * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
4.578 + */
4.579 + private static <T> int gallopRight(T key, T[] a, int base, int len,
4.580 + int hint, Comparator<? super T> c) {
4.581 + assert len > 0 && hint >= 0 && hint < len;
4.582 +
4.583 + int ofs = 1;
4.584 + int lastOfs = 0;
4.585 + if (c.compare(key, a[base + hint]) < 0) {
4.586 + // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
4.587 + int maxOfs = hint + 1;
4.588 + while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) {
4.589 + lastOfs = ofs;
4.590 + ofs = (ofs << 1) + 1;
4.591 + if (ofs <= 0) // int overflow
4.592 + ofs = maxOfs;
4.593 + }
4.594 + if (ofs > maxOfs)
4.595 + ofs = maxOfs;
4.596 +
4.597 + // Make offsets relative to b
4.598 + int tmp = lastOfs;
4.599 + lastOfs = hint - ofs;
4.600 + ofs = hint - tmp;
4.601 + } else { // a[b + hint] <= key
4.602 + // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
4.603 + int maxOfs = len - hint;
4.604 + while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) {
4.605 + lastOfs = ofs;
4.606 + ofs = (ofs << 1) + 1;
4.607 + if (ofs <= 0) // int overflow
4.608 + ofs = maxOfs;
4.609 + }
4.610 + if (ofs > maxOfs)
4.611 + ofs = maxOfs;
4.612 +
4.613 + // Make offsets relative to b
4.614 + lastOfs += hint;
4.615 + ofs += hint;
4.616 + }
4.617 + assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
4.618 +
4.619 + /*
4.620 + * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
4.621 + * the right of lastOfs but no farther right than ofs. Do a binary
4.622 + * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
4.623 + */
4.624 + lastOfs++;
4.625 + while (lastOfs < ofs) {
4.626 + int m = lastOfs + ((ofs - lastOfs) >>> 1);
4.627 +
4.628 + if (c.compare(key, a[base + m]) < 0)
4.629 + ofs = m; // key < a[b + m]
4.630 + else
4.631 + lastOfs = m + 1; // a[b + m] <= key
4.632 + }
4.633 + assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
4.634 + return ofs;
4.635 + }
4.636 +
4.637 + /**
4.638 + * Merges two adjacent runs in place, in a stable fashion. The first
4.639 + * element of the first run must be greater than the first element of the
4.640 + * second run (a[base1] > a[base2]), and the last element of the first run
4.641 + * (a[base1 + len1-1]) must be greater than all elements of the second run.
4.642 + *
4.643 + * For performance, this method should be called only when len1 <= len2;
4.644 + * its twin, mergeHi should be called if len1 >= len2. (Either method
4.645 + * may be called if len1 == len2.)
4.646 + *
4.647 + * @param base1 index of first element in first run to be merged
4.648 + * @param len1 length of first run to be merged (must be > 0)
4.649 + * @param base2 index of first element in second run to be merged
4.650 + * (must be aBase + aLen)
4.651 + * @param len2 length of second run to be merged (must be > 0)
4.652 + */
4.653 + private void mergeLo(int base1, int len1, int base2, int len2) {
4.654 + assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
4.655 +
4.656 + // Copy first run into temp array
4.657 + T[] a = this.a; // For performance
4.658 + T[] tmp = ensureCapacity(len1);
4.659 + System.arraycopy(a, base1, tmp, 0, len1);
4.660 +
4.661 + int cursor1 = 0; // Indexes into tmp array
4.662 + int cursor2 = base2; // Indexes int a
4.663 + int dest = base1; // Indexes int a
4.664 +
4.665 + // Move first element of second run and deal with degenerate cases
4.666 + a[dest++] = a[cursor2++];
4.667 + if (--len2 == 0) {
4.668 + System.arraycopy(tmp, cursor1, a, dest, len1);
4.669 + return;
4.670 + }
4.671 + if (len1 == 1) {
4.672 + System.arraycopy(a, cursor2, a, dest, len2);
4.673 + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
4.674 + return;
4.675 + }
4.676 +
4.677 + Comparator<? super T> c = this.c; // Use local variable for performance
4.678 + int minGallop = this.minGallop; // " " " " "
4.679 + outer:
4.680 + while (true) {
4.681 + int count1 = 0; // Number of times in a row that first run won
4.682 + int count2 = 0; // Number of times in a row that second run won
4.683 +
4.684 + /*
4.685 + * Do the straightforward thing until (if ever) one run starts
4.686 + * winning consistently.
4.687 + */
4.688 + do {
4.689 + assert len1 > 1 && len2 > 0;
4.690 + if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
4.691 + a[dest++] = a[cursor2++];
4.692 + count2++;
4.693 + count1 = 0;
4.694 + if (--len2 == 0)
4.695 + break outer;
4.696 + } else {
4.697 + a[dest++] = tmp[cursor1++];
4.698 + count1++;
4.699 + count2 = 0;
4.700 + if (--len1 == 1)
4.701 + break outer;
4.702 + }
4.703 + } while ((count1 | count2) < minGallop);
4.704 +
4.705 + /*
4.706 + * One run is winning so consistently that galloping may be a
4.707 + * huge win. So try that, and continue galloping until (if ever)
4.708 + * neither run appears to be winning consistently anymore.
4.709 + */
4.710 + do {
4.711 + assert len1 > 1 && len2 > 0;
4.712 + count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
4.713 + if (count1 != 0) {
4.714 + System.arraycopy(tmp, cursor1, a, dest, count1);
4.715 + dest += count1;
4.716 + cursor1 += count1;
4.717 + len1 -= count1;
4.718 + if (len1 <= 1) // len1 == 1 || len1 == 0
4.719 + break outer;
4.720 + }
4.721 + a[dest++] = a[cursor2++];
4.722 + if (--len2 == 0)
4.723 + break outer;
4.724 +
4.725 + count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
4.726 + if (count2 != 0) {
4.727 + System.arraycopy(a, cursor2, a, dest, count2);
4.728 + dest += count2;
4.729 + cursor2 += count2;
4.730 + len2 -= count2;
4.731 + if (len2 == 0)
4.732 + break outer;
4.733 + }
4.734 + a[dest++] = tmp[cursor1++];
4.735 + if (--len1 == 1)
4.736 + break outer;
4.737 + minGallop--;
4.738 + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
4.739 + if (minGallop < 0)
4.740 + minGallop = 0;
4.741 + minGallop += 2; // Penalize for leaving gallop mode
4.742 + } // End of "outer" loop
4.743 + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
4.744 +
4.745 + if (len1 == 1) {
4.746 + assert len2 > 0;
4.747 + System.arraycopy(a, cursor2, a, dest, len2);
4.748 + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
4.749 + } else if (len1 == 0) {
4.750 + throw new IllegalArgumentException(
4.751 + "Comparison method violates its general contract!");
4.752 + } else {
4.753 + assert len2 == 0;
4.754 + assert len1 > 1;
4.755 + System.arraycopy(tmp, cursor1, a, dest, len1);
4.756 + }
4.757 + }
4.758 +
4.759 + /**
4.760 + * Like mergeLo, except that this method should be called only if
4.761 + * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
4.762 + * may be called if len1 == len2.)
4.763 + *
4.764 + * @param base1 index of first element in first run to be merged
4.765 + * @param len1 length of first run to be merged (must be > 0)
4.766 + * @param base2 index of first element in second run to be merged
4.767 + * (must be aBase + aLen)
4.768 + * @param len2 length of second run to be merged (must be > 0)
4.769 + */
4.770 + private void mergeHi(int base1, int len1, int base2, int len2) {
4.771 + assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
4.772 +
4.773 + // Copy second run into temp array
4.774 + T[] a = this.a; // For performance
4.775 + T[] tmp = ensureCapacity(len2);
4.776 + System.arraycopy(a, base2, tmp, 0, len2);
4.777 +
4.778 + int cursor1 = base1 + len1 - 1; // Indexes into a
4.779 + int cursor2 = len2 - 1; // Indexes into tmp array
4.780 + int dest = base2 + len2 - 1; // Indexes into a
4.781 +
4.782 + // Move last element of first run and deal with degenerate cases
4.783 + a[dest--] = a[cursor1--];
4.784 + if (--len1 == 0) {
4.785 + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
4.786 + return;
4.787 + }
4.788 + if (len2 == 1) {
4.789 + dest -= len1;
4.790 + cursor1 -= len1;
4.791 + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
4.792 + a[dest] = tmp[cursor2];
4.793 + return;
4.794 + }
4.795 +
4.796 + Comparator<? super T> c = this.c; // Use local variable for performance
4.797 + int minGallop = this.minGallop; // " " " " "
4.798 + outer:
4.799 + while (true) {
4.800 + int count1 = 0; // Number of times in a row that first run won
4.801 + int count2 = 0; // Number of times in a row that second run won
4.802 +
4.803 + /*
4.804 + * Do the straightforward thing until (if ever) one run
4.805 + * appears to win consistently.
4.806 + */
4.807 + do {
4.808 + assert len1 > 0 && len2 > 1;
4.809 + if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
4.810 + a[dest--] = a[cursor1--];
4.811 + count1++;
4.812 + count2 = 0;
4.813 + if (--len1 == 0)
4.814 + break outer;
4.815 + } else {
4.816 + a[dest--] = tmp[cursor2--];
4.817 + count2++;
4.818 + count1 = 0;
4.819 + if (--len2 == 1)
4.820 + break outer;
4.821 + }
4.822 + } while ((count1 | count2) < minGallop);
4.823 +
4.824 + /*
4.825 + * One run is winning so consistently that galloping may be a
4.826 + * huge win. So try that, and continue galloping until (if ever)
4.827 + * neither run appears to be winning consistently anymore.
4.828 + */
4.829 + do {
4.830 + assert len1 > 0 && len2 > 1;
4.831 + count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
4.832 + if (count1 != 0) {
4.833 + dest -= count1;
4.834 + cursor1 -= count1;
4.835 + len1 -= count1;
4.836 + System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
4.837 + if (len1 == 0)
4.838 + break outer;
4.839 + }
4.840 + a[dest--] = tmp[cursor2--];
4.841 + if (--len2 == 1)
4.842 + break outer;
4.843 +
4.844 + count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c);
4.845 + if (count2 != 0) {
4.846 + dest -= count2;
4.847 + cursor2 -= count2;
4.848 + len2 -= count2;
4.849 + System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
4.850 + if (len2 <= 1) // len2 == 1 || len2 == 0
4.851 + break outer;
4.852 + }
4.853 + a[dest--] = a[cursor1--];
4.854 + if (--len1 == 0)
4.855 + break outer;
4.856 + minGallop--;
4.857 + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
4.858 + if (minGallop < 0)
4.859 + minGallop = 0;
4.860 + minGallop += 2; // Penalize for leaving gallop mode
4.861 + } // End of "outer" loop
4.862 + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
4.863 +
4.864 + if (len2 == 1) {
4.865 + assert len1 > 0;
4.866 + dest -= len1;
4.867 + cursor1 -= len1;
4.868 + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
4.869 + a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
4.870 + } else if (len2 == 0) {
4.871 + throw new IllegalArgumentException(
4.872 + "Comparison method violates its general contract!");
4.873 + } else {
4.874 + assert len1 == 0;
4.875 + assert len2 > 0;
4.876 + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
4.877 + }
4.878 + }
4.879 +
4.880 + /**
4.881 + * Ensures that the external array tmp has at least the specified
4.882 + * number of elements, increasing its size if necessary. The size
4.883 + * increases exponentially to ensure amortized linear time complexity.
4.884 + *
4.885 + * @param minCapacity the minimum required capacity of the tmp array
4.886 + * @return tmp, whether or not it grew
4.887 + */
4.888 + private T[] ensureCapacity(int minCapacity) {
4.889 + if (tmp.length < minCapacity) {
4.890 + // Compute smallest power of 2 > minCapacity
4.891 + int newSize = minCapacity;
4.892 + newSize |= newSize >> 1;
4.893 + newSize |= newSize >> 2;
4.894 + newSize |= newSize >> 4;
4.895 + newSize |= newSize >> 8;
4.896 + newSize |= newSize >> 16;
4.897 + newSize++;
4.898 +
4.899 + if (newSize < 0) // Not bloody likely!
4.900 + newSize = minCapacity;
4.901 + else
4.902 + newSize = Math.min(newSize, a.length >>> 1);
4.903 +
4.904 + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
4.905 + T[] newArray = (T[]) new Object[newSize];
4.906 + tmp = newArray;
4.907 + }
4.908 + return tmp;
4.909 + }
4.910 +
4.911 + /**
4.912 + * Checks that fromIndex and toIndex are in range, and throws an
4.913 + * appropriate exception if they aren't.
4.914 + *
4.915 + * @param arrayLen the length of the array
4.916 + * @param fromIndex the index of the first element of the range
4.917 + * @param toIndex the index after the last element of the range
4.918 + * @throws IllegalArgumentException if fromIndex > toIndex
4.919 + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
4.920 + * or toIndex > arrayLen
4.921 + */
4.922 + private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
4.923 + if (fromIndex > toIndex)
4.924 + throw new IllegalArgumentException("fromIndex(" + fromIndex +
4.925 + ") > toIndex(" + toIndex+")");
4.926 + if (fromIndex < 0)
4.927 + throw new ArrayIndexOutOfBoundsException(fromIndex);
4.928 + if (toIndex > arrayLen)
4.929 + throw new ArrayIndexOutOfBoundsException(toIndex);
4.930 + }
4.931 +}