| /* |
| * Copyright (c) 2009, 2013, 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. |
| * |
| * All exposed methods are package-private, designed to be invoked |
| * from public methods (in class Arrays) after performing any |
| * necessary array bounds checks and expanding parameters into the |
| * required forms. |
| * |
| * @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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(int[] a, int left, int right, |
| int[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| int[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new int[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| int[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(long[] a, int left, int right, |
| long[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| long[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new long[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| long[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(short[] a, int left, int right, |
| short[] work, int workBase, int workLen) { |
| // 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, work, workBase, workLen); |
| } |
| } |
| |
| /** 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 |
| * @param work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| private static void doSort(short[] a, int left, int right, |
| short[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| short[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new short[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| short[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(char[] a, int left, int right, |
| char[] work, int workBase, int workLen) { |
| // 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, work, workBase, workLen); |
| } |
| } |
| |
| /** 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 |
| * @param work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| private static void doSort(char[] a, int left, int right, |
| char[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| char[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new char[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| char[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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 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 |
| */ |
| 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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(float[] a, int left, int right, |
| float[] work, int workBase, int workLen) { |
| /* |
| * 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, work, workBase, workLen); |
| |
| /* |
| * 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 |
| * @param work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| private static void doSort(float[] a, int left, int right, |
| float[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| float[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new float[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| float[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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 range of the array using the given |
| * workspace array slice if possible for merging |
| * |
| * @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 work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| static void sort(double[] a, int left, int right, |
| double[] work, int workBase, int workLen) { |
| /* |
| * 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, work, workBase, workLen); |
| |
| /* |
| * 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 |
| * @param work a workspace array (slice) |
| * @param workBase origin of usable space in work array |
| * @param workLen usable size of work array |
| */ |
| private static void doSort(double[] a, int left, int right, |
| double[] work, int workBase, int workLen) { |
| // 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 |
| // Implementation note: variable "right" is increased by 1. |
| if (run[count] == right++) { // The last run contains one element |
| run[++count] = right; |
| } else if (count == 1) { // The array is already sorted |
| return; |
| } |
| |
| // Determine alternation base for merge |
| byte odd = 0; |
| for (int n = 1; (n <<= 1) < count; odd ^= 1); |
| |
| // Use or create temporary array b for merging |
| double[] b; // temp array; alternates with a |
| int ao, bo; // array offsets from 'left' |
| int blen = right - left; // space needed for b |
| if (work == null || workLen < blen || workBase + blen > work.length) { |
| work = new double[blen]; |
| workBase = 0; |
| } |
| if (odd == 0) { |
| System.arraycopy(a, left, work, workBase, blen); |
| b = a; |
| bo = 0; |
| a = work; |
| ao = workBase - left; |
| } else { |
| b = work; |
| ao = 0; |
| bo = workBase - left; |
| } |
| |
| // 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 + ao] <= a[q + ao]) { |
| b[i + bo] = a[p++ + ao]; |
| } else { |
| b[i + bo] = a[q++ + ao]; |
| } |
| } |
| run[++last] = hi; |
| } |
| if ((count & 1) != 0) { |
| for (int i = right, lo = run[count - 1]; --i >= lo; |
| b[i + bo] = a[i + ao] |
| ); |
| run[++last] = right; |
| } |
| double[] t = a; a = b; b = t; |
| int o = ao; ao = bo; bo = o; |
| } |
| } |
| |
| /** |
| * 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); |
| } |
| } |
| } |