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