8226297: Dual-pivot quicksort improvements
Reviewed-by: dl, lbourges
Contributed-by: Vladimir Yaroslavskiy <vlv.spb.ru@mail.ru>
/*
* Copyright (c) 2009, 2019, 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;
import java.util.concurrent.CountedCompleter;
import java.util.concurrent.RecursiveTask;
/**
* This class implements powerful and fully optimized versions, both
* sequential and parallel, of the Dual-Pivot Quicksort algorithm by
* Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
* offers O(n log(n)) performance on all data sets, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* There are also additional algorithms, invoked from the Dual-Pivot
* Quicksort, such as mixed insertion sort, merging of runs and heap
* sort, counting sort and parallel merge sort.
*
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
* @author Doug Lea
*
* @version 2018.08.18
*
* @since 1.7 * 14
*/
final class DualPivotQuicksort {
/**
* Prevents instantiation.
*/
private DualPivotQuicksort() {}
/**
* Max array size to use mixed insertion sort.
*/
private static final int MAX_MIXED_INSERTION_SORT_SIZE = 65;
/**
* Max array size to use insertion sort.
*/
private static final int MAX_INSERTION_SORT_SIZE = 44;
/**
* Min array size to perform sorting in parallel.
*/
private static final int MIN_PARALLEL_SORT_SIZE = 4 << 10;
/**
* Min array size to try merging of runs.
*/
private static final int MIN_TRY_MERGE_SIZE = 4 << 10;
/**
* Min size of the first run to continue with scanning.
*/
private static final int MIN_FIRST_RUN_SIZE = 16;
/**
* Min factor for the first runs to continue scanning.
*/
private static final int MIN_FIRST_RUNS_FACTOR = 7;
/**
* Max capacity of the index array for tracking runs.
*/
private static final int MAX_RUN_CAPACITY = 5 << 10;
/**
* Min number of runs, required by parallel merging.
*/
private static final int MIN_RUN_COUNT = 4;
/**
* Min array size to use parallel merging of parts.
*/
private static final int MIN_PARALLEL_MERGE_PARTS_SIZE = 4 << 10;
/**
* Min size of a byte array to use counting sort.
*/
private static final int MIN_BYTE_COUNTING_SORT_SIZE = 64;
/**
* Min size of a short or char array to use counting sort.
*/
private static final int MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE = 1750;
/**
* Threshold of mixed insertion sort is incremented by this value.
*/
private static final int DELTA = 3 << 1;
/**
* Max recursive partitioning depth before using heap sort.
*/
private static final int MAX_RECURSION_DEPTH = 64 * DELTA;
/**
* Calculates the double depth of parallel merging.
* Depth is negative, if tasks split before sorting.
*
* @param parallelism the parallelism level
* @param size the target size
* @return the depth of parallel merging
*/
private static int getDepth(int parallelism, int size) {
int depth = 0;
while ((parallelism >>= 3) > 0 && (size >>= 2) > 0) {
depth -= 2;
}
return depth;
}
/**
* Sorts the specified range of the array using parallel merge
* sort and/or Dual-Pivot Quicksort.
*
* To balance the faster splitting and parallelism of merge sort
* with the faster element partitioning of Quicksort, ranges are
* subdivided in tiers such that, if there is enough parallelism,
* the four-way parallel merge is started, still ensuring enough
* parallelism to process the partitions.
*
* @param a the array to be sorted
* @param parallelism the parallelism level
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(int[] a, int parallelism, int low, int high) {
int size = high - low;
if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
int depth = getDepth(parallelism, size >> 12);
int[] b = depth == 0 ? null : new int[size];
new Sorter(null, a, b, low, size, low, depth).invoke();
} else {
sort(null, a, 0, low, high);
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(Sorter sorter, int[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Run mixed insertion sort on small non-leftmost parts.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Check if the whole array or large non-leftmost
* parts are nearly sorted and then merge runs.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* Switch to heap sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
int a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { int t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { int t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { int t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
int pivot1 = a[e1];
int pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
int ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively (possibly in parallel),
* excluding known pivots.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, lower + 1, upper);
sorter.forkSorter(bits | 1, upper + 1, high);
} else {
sort(sorter, a, bits | 1, lower + 1, upper);
sort(sorter, a, bits | 1, upper + 1, high);
}
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
int pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
int ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part (possibly in parallel), excluding
* known pivot. All elements from the central part are
* equal and therefore already sorted.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, upper, high);
} else {
sort(sorter, a, bits | 1, upper, high);
}
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using mixed insertion sort.
*
* Mixed insertion sort is combination of simple insertion sort,
* pin insertion sort and pair insertion sort.
*
* In the context of Dual-Pivot Quicksort, the pivot element
* from the left part plays the role of sentinel, because it
* is less than any elements from the given part. Therefore,
* expensive check of the left range can be skipped on each
* iteration unless it is the leftmost call.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param end the index of the last element for simple insertion sort
* @param high the index of the last element, exclusive, to be sorted
*/
private static void mixedInsertionSort(int[] a, int low, int end, int high) {
if (end == high) {
/*
* Invoke simple insertion sort on tiny array.
*/
for (int i; ++low < end; ) {
int ai = a[i = low];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
} else {
/*
* Start with pin insertion sort on small part.
*
* Pin insertion sort is extended simple insertion sort.
* The main idea of this sort is to put elements larger
* than an element called pin to the end of array (the
* proper area for such elements). It avoids expensive
* movements of these elements through the whole array.
*/
int pin = a[end];
for (int i, p = high; ++low < end; ) {
int ai = a[i = low];
if (ai < a[i - 1]) { // Small element
/*
* Insert small element into sorted part.
*/
a[i] = a[--i];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
} else if (p > i && ai > pin) { // Large element
/*
* Find element smaller than pin.
*/
while (a[--p] > pin);
/*
* Swap it with large element.
*/
if (p > i) {
ai = a[p];
a[p] = a[i];
}
/*
* Insert small element into sorted part.
*/
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
/*
* Continue with pair insertion sort on remain part.
*/
for (int i; low < high; ++low) {
int a1 = a[i = low], a2 = a[++low];
/*
* Insert two elements per iteration: at first, insert the
* larger element and then insert the smaller element, but
* from the position where the larger element was inserted.
*/
if (a1 > a2) {
while (a1 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a1;
while (a2 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a2;
} else if (a1 < a[i - 1]) {
while (a2 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a2;
while (a1 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a1;
}
}
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(int[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
int ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* Sorts the specified range of the array using heap sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void heapSort(int[] a, int low, int high) {
for (int k = (low + high) >>> 1; k > low; ) {
pushDown(a, --k, a[k], low, high);
}
while (--high > low) {
int max = a[low];
pushDown(a, low, a[high], low, high);
a[high] = max;
}
}
/**
* Pushes specified element down during heap sort.
*
* @param a the given array
* @param p the start index
* @param value the given element
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void pushDown(int[] a, int p, int value, int low, int high) {
for (int k ;; a[p] = a[p = k]) {
k = (p << 1) - low + 2; // Index of the right child
if (k > high) {
break;
}
if (k == high || a[k] < a[k - 1]) {
--k;
}
if (a[k] <= value) {
break;
}
}
a[p] = value;
}
/**
* Tries to sort the specified range of the array.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param low the index of the first element to be sorted
* @param size the array size
* @return true if finally sorted, false otherwise
*/
private static boolean tryMergeRuns(Sorter sorter, int[] a, int low, int size) {
/*
* The run array is constructed only if initial runs are
* long enough to continue, run[i] then holds start index
* of the i-th sequence of elements in non-descending order.
*/
int[] run = null;
int high = low + size;
int count = 1, last = low;
/*
* Identify all possible runs.
*/
for (int k = low + 1; k < high; ) {
/*
* Find the end index of the current run.
*/
if (a[k - 1] < a[k]) {
// Identify ascending sequence
while (++k < high && a[k - 1] <= a[k]);
} else if (a[k - 1] > a[k]) {
// Identify descending sequence
while (++k < high && a[k - 1] >= a[k]);
// Reverse into ascending order
for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
int ai = a[i]; a[i] = a[j]; a[j] = ai;
}
} else { // Identify constant sequence
for (int ak = a[k]; ++k < high && ak == a[k]; );
if (k < high) {
continue;
}
}
/*
* Check special cases.
*/
if (run == null) {
if (k == high) {
/*
* The array is monotonous sequence,
* and therefore already sorted.
*/
return true;
}
if (k - low < MIN_FIRST_RUN_SIZE) {
/*
* The first run is too small
* to proceed with scanning.
*/
return false;
}
run = new int[((size >> 10) | 0x7F) & 0x3FF];
run[0] = low;
} else if (a[last - 1] > a[last]) {
if (count > (k - low) >> MIN_FIRST_RUNS_FACTOR) {
/*
* The first runs are not long
* enough to continue scanning.
*/
return false;
}
if (++count == MAX_RUN_CAPACITY) {
/*
* Array is not highly structured.
*/
return false;
}
if (count == run.length) {
/*
* Increase capacity of index array.
*/
run = Arrays.copyOf(run, count << 1);
}
}
run[count] = (last = k);
}
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
int[] b; int offset = low;
if (sorter == null || (b = (int[]) sorter.b) == null) {
b = new int[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
}
/**
* Merges the specified runs.
*
* @param a the source array
* @param b the temporary buffer used in merging
* @param offset the start index in the source, inclusive
* @param aim specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)
* @param parallel indicates whether merging is performed in parallel
* @param run the start indexes of the runs, inclusive
* @param lo the start index of the first run, inclusive
* @param hi the start index of the last run, inclusive
* @return the destination where runs are merged
*/
private static int[] mergeRuns(int[] a, int[] b, int offset,
int aim, boolean parallel, int[] run, int lo, int hi) {
if (hi - lo == 1) {
if (aim >= 0) {
return a;
}
for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
b[--j] = a[--i]
);
return b;
}
/*
* Split into approximately equal parts.
*/
int mi = lo, rmi = (run[lo] + run[hi]) >>> 1;
while (run[++mi + 1] <= rmi);
/*
* Merge the left and right parts.
*/
int[] a1, a2;
if (parallel && hi - lo > MIN_RUN_COUNT) {
RunMerger merger = new RunMerger(a, b, offset, 0, run, mi, hi).forkMe();
a1 = mergeRuns(a, b, offset, -aim, true, run, lo, mi);
a2 = (int[]) merger.getDestination();
} else {
a1 = mergeRuns(a, b, offset, -aim, false, run, lo, mi);
a2 = mergeRuns(a, b, offset, 0, false, run, mi, hi);
}
int[] dst = a1 == a ? b : a;
int k = a1 == a ? run[lo] - offset : run[lo];
int lo1 = a1 == b ? run[lo] - offset : run[lo];
int hi1 = a1 == b ? run[mi] - offset : run[mi];
int lo2 = a2 == b ? run[mi] - offset : run[mi];
int hi2 = a2 == b ? run[hi] - offset : run[hi];
if (parallel) {
new Merger(null, dst, k, a1, lo1, hi1, a2, lo2, hi2).invoke();
} else {
mergeParts(null, dst, k, a1, lo1, hi1, a2, lo2, hi2);
}
return dst;
}
/**
* Merges the sorted parts.
*
* @param merger parallel context
* @param dst the destination where parts are merged
* @param k the start index of the destination, inclusive
* @param a1 the first part
* @param lo1 the start index of the first part, inclusive
* @param hi1 the end index of the first part, exclusive
* @param a2 the second part
* @param lo2 the start index of the second part, inclusive
* @param hi2 the end index of the second part, exclusive
*/
private static void mergeParts(Merger merger, int[] dst, int k,
int[] a1, int lo1, int hi1, int[] a2, int lo2, int hi2) {
if (merger != null && a1 == a2) {
while (true) {
/*
* The first part must be larger.
*/
if (hi1 - lo1 < hi2 - lo2) {
int lo = lo1; lo1 = lo2; lo2 = lo;
int hi = hi1; hi1 = hi2; hi2 = hi;
}
/*
* Small parts will be merged sequentially.
*/
if (hi1 - lo1 < MIN_PARALLEL_MERGE_PARTS_SIZE) {
break;
}
/*
* Find the median of the larger part.
*/
int mi1 = (lo1 + hi1) >>> 1;
int key = a1[mi1];
int mi2 = hi2;
/*
* Partition the smaller part.
*/
for (int loo = lo2; loo < mi2; ) {
int t = (loo + mi2) >>> 1;
if (key > a2[t]) {
loo = t + 1;
} else {
mi2 = t;
}
}
int d = mi2 - lo2 + mi1 - lo1;
/*
* Merge the right sub-parts in parallel.
*/
merger.forkMerger(dst, k + d, a1, mi1, hi1, a2, mi2, hi2);
/*
* Process the sub-left parts.
*/
hi1 = mi1;
hi2 = mi2;
}
}
/*
* Merge small parts sequentially.
*/
while (lo1 < hi1 && lo2 < hi2) {
dst[k++] = a1[lo1] < a2[lo2] ? a1[lo1++] : a2[lo2++];
}
if (dst != a1 || k < lo1) {
while (lo1 < hi1) {
dst[k++] = a1[lo1++];
}
}
if (dst != a2 || k < lo2) {
while (lo2 < hi2) {
dst[k++] = a2[lo2++];
}
}
}
// [long]
/**
* Sorts the specified range of the array using parallel merge
* sort and/or Dual-Pivot Quicksort.
*
* To balance the faster splitting and parallelism of merge sort
* with the faster element partitioning of Quicksort, ranges are
* subdivided in tiers such that, if there is enough parallelism,
* the four-way parallel merge is started, still ensuring enough
* parallelism to process the partitions.
*
* @param a the array to be sorted
* @param parallelism the parallelism level
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(long[] a, int parallelism, int low, int high) {
int size = high - low;
if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
int depth = getDepth(parallelism, size >> 12);
long[] b = depth == 0 ? null : new long[size];
new Sorter(null, a, b, low, size, low, depth).invoke();
} else {
sort(null, a, 0, low, high);
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(Sorter sorter, long[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Run mixed insertion sort on small non-leftmost parts.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Check if the whole array or large non-leftmost
* parts are nearly sorted and then merge runs.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* Switch to heap sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
long a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { long t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { long t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { long t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
long pivot1 = a[e1];
long pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
long ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively (possibly in parallel),
* excluding known pivots.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, lower + 1, upper);
sorter.forkSorter(bits | 1, upper + 1, high);
} else {
sort(sorter, a, bits | 1, lower + 1, upper);
sort(sorter, a, bits | 1, upper + 1, high);
}
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
long pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
long ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part (possibly in parallel), excluding
* known pivot. All elements from the central part are
* equal and therefore already sorted.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, upper, high);
} else {
sort(sorter, a, bits | 1, upper, high);
}
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using mixed insertion sort.
*
* Mixed insertion sort is combination of simple insertion sort,
* pin insertion sort and pair insertion sort.
*
* In the context of Dual-Pivot Quicksort, the pivot element
* from the left part plays the role of sentinel, because it
* is less than any elements from the given part. Therefore,
* expensive check of the left range can be skipped on each
* iteration unless it is the leftmost call.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param end the index of the last element for simple insertion sort
* @param high the index of the last element, exclusive, to be sorted
*/
private static void mixedInsertionSort(long[] a, int low, int end, int high) {
if (end == high) {
/*
* Invoke simple insertion sort on tiny array.
*/
for (int i; ++low < end; ) {
long ai = a[i = low];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
} else {
/*
* Start with pin insertion sort on small part.
*
* Pin insertion sort is extended simple insertion sort.
* The main idea of this sort is to put elements larger
* than an element called pin to the end of array (the
* proper area for such elements). It avoids expensive
* movements of these elements through the whole array.
*/
long pin = a[end];
for (int i, p = high; ++low < end; ) {
long ai = a[i = low];
if (ai < a[i - 1]) { // Small element
/*
* Insert small element into sorted part.
*/
a[i] = a[--i];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
} else if (p > i && ai > pin) { // Large element
/*
* Find element smaller than pin.
*/
while (a[--p] > pin);
/*
* Swap it with large element.
*/
if (p > i) {
ai = a[p];
a[p] = a[i];
}
/*
* Insert small element into sorted part.
*/
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
/*
* Continue with pair insertion sort on remain part.
*/
for (int i; low < high; ++low) {
long a1 = a[i = low], a2 = a[++low];
/*
* Insert two elements per iteration: at first, insert the
* larger element and then insert the smaller element, but
* from the position where the larger element was inserted.
*/
if (a1 > a2) {
while (a1 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a1;
while (a2 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a2;
} else if (a1 < a[i - 1]) {
while (a2 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a2;
while (a1 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a1;
}
}
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(long[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
long ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* Sorts the specified range of the array using heap sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void heapSort(long[] a, int low, int high) {
for (int k = (low + high) >>> 1; k > low; ) {
pushDown(a, --k, a[k], low, high);
}
while (--high > low) {
long max = a[low];
pushDown(a, low, a[high], low, high);
a[high] = max;
}
}
/**
* Pushes specified element down during heap sort.
*
* @param a the given array
* @param p the start index
* @param value the given element
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void pushDown(long[] a, int p, long value, int low, int high) {
for (int k ;; a[p] = a[p = k]) {
k = (p << 1) - low + 2; // Index of the right child
if (k > high) {
break;
}
if (k == high || a[k] < a[k - 1]) {
--k;
}
if (a[k] <= value) {
break;
}
}
a[p] = value;
}
/**
* Tries to sort the specified range of the array.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param low the index of the first element to be sorted
* @param size the array size
* @return true if finally sorted, false otherwise
*/
private static boolean tryMergeRuns(Sorter sorter, long[] a, int low, int size) {
/*
* The run array is constructed only if initial runs are
* long enough to continue, run[i] then holds start index
* of the i-th sequence of elements in non-descending order.
*/
int[] run = null;
int high = low + size;
int count = 1, last = low;
/*
* Identify all possible runs.
*/
for (int k = low + 1; k < high; ) {
/*
* Find the end index of the current run.
*/
if (a[k - 1] < a[k]) {
// Identify ascending sequence
while (++k < high && a[k - 1] <= a[k]);
} else if (a[k - 1] > a[k]) {
// Identify descending sequence
while (++k < high && a[k - 1] >= a[k]);
// Reverse into ascending order
for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
long ai = a[i]; a[i] = a[j]; a[j] = ai;
}
} else { // Identify constant sequence
for (long ak = a[k]; ++k < high && ak == a[k]; );
if (k < high) {
continue;
}
}
/*
* Check special cases.
*/
if (run == null) {
if (k == high) {
/*
* The array is monotonous sequence,
* and therefore already sorted.
*/
return true;
}
if (k - low < MIN_FIRST_RUN_SIZE) {
/*
* The first run is too small
* to proceed with scanning.
*/
return false;
}
run = new int[((size >> 10) | 0x7F) & 0x3FF];
run[0] = low;
} else if (a[last - 1] > a[last]) {
if (count > (k - low) >> MIN_FIRST_RUNS_FACTOR) {
/*
* The first runs are not long
* enough to continue scanning.
*/
return false;
}
if (++count == MAX_RUN_CAPACITY) {
/*
* Array is not highly structured.
*/
return false;
}
if (count == run.length) {
/*
* Increase capacity of index array.
*/
run = Arrays.copyOf(run, count << 1);
}
}
run[count] = (last = k);
}
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
long[] b; int offset = low;
if (sorter == null || (b = (long[]) sorter.b) == null) {
b = new long[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
}
/**
* Merges the specified runs.
*
* @param a the source array
* @param b the temporary buffer used in merging
* @param offset the start index in the source, inclusive
* @param aim specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)
* @param parallel indicates whether merging is performed in parallel
* @param run the start indexes of the runs, inclusive
* @param lo the start index of the first run, inclusive
* @param hi the start index of the last run, inclusive
* @return the destination where runs are merged
*/
private static long[] mergeRuns(long[] a, long[] b, int offset,
int aim, boolean parallel, int[] run, int lo, int hi) {
if (hi - lo == 1) {
if (aim >= 0) {
return a;
}
for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
b[--j] = a[--i]
);
return b;
}
/*
* Split into approximately equal parts.
*/
int mi = lo, rmi = (run[lo] + run[hi]) >>> 1;
while (run[++mi + 1] <= rmi);
/*
* Merge the left and right parts.
*/
long[] a1, a2;
if (parallel && hi - lo > MIN_RUN_COUNT) {
RunMerger merger = new RunMerger(a, b, offset, 0, run, mi, hi).forkMe();
a1 = mergeRuns(a, b, offset, -aim, true, run, lo, mi);
a2 = (long[]) merger.getDestination();
} else {
a1 = mergeRuns(a, b, offset, -aim, false, run, lo, mi);
a2 = mergeRuns(a, b, offset, 0, false, run, mi, hi);
}
long[] dst = a1 == a ? b : a;
int k = a1 == a ? run[lo] - offset : run[lo];
int lo1 = a1 == b ? run[lo] - offset : run[lo];
int hi1 = a1 == b ? run[mi] - offset : run[mi];
int lo2 = a2 == b ? run[mi] - offset : run[mi];
int hi2 = a2 == b ? run[hi] - offset : run[hi];
if (parallel) {
new Merger(null, dst, k, a1, lo1, hi1, a2, lo2, hi2).invoke();
} else {
mergeParts(null, dst, k, a1, lo1, hi1, a2, lo2, hi2);
}
return dst;
}
/**
* Merges the sorted parts.
*
* @param merger parallel context
* @param dst the destination where parts are merged
* @param k the start index of the destination, inclusive
* @param a1 the first part
* @param lo1 the start index of the first part, inclusive
* @param hi1 the end index of the first part, exclusive
* @param a2 the second part
* @param lo2 the start index of the second part, inclusive
* @param hi2 the end index of the second part, exclusive
*/
private static void mergeParts(Merger merger, long[] dst, int k,
long[] a1, int lo1, int hi1, long[] a2, int lo2, int hi2) {
if (merger != null && a1 == a2) {
while (true) {
/*
* The first part must be larger.
*/
if (hi1 - lo1 < hi2 - lo2) {
int lo = lo1; lo1 = lo2; lo2 = lo;
int hi = hi1; hi1 = hi2; hi2 = hi;
}
/*
* Small parts will be merged sequentially.
*/
if (hi1 - lo1 < MIN_PARALLEL_MERGE_PARTS_SIZE) {
break;
}
/*
* Find the median of the larger part.
*/
int mi1 = (lo1 + hi1) >>> 1;
long key = a1[mi1];
int mi2 = hi2;
/*
* Partition the smaller part.
*/
for (int loo = lo2; loo < mi2; ) {
int t = (loo + mi2) >>> 1;
if (key > a2[t]) {
loo = t + 1;
} else {
mi2 = t;
}
}
int d = mi2 - lo2 + mi1 - lo1;
/*
* Merge the right sub-parts in parallel.
*/
merger.forkMerger(dst, k + d, a1, mi1, hi1, a2, mi2, hi2);
/*
* Process the sub-left parts.
*/
hi1 = mi1;
hi2 = mi2;
}
}
/*
* Merge small parts sequentially.
*/
while (lo1 < hi1 && lo2 < hi2) {
dst[k++] = a1[lo1] < a2[lo2] ? a1[lo1++] : a2[lo2++];
}
if (dst != a1 || k < lo1) {
while (lo1 < hi1) {
dst[k++] = a1[lo1++];
}
}
if (dst != a2 || k < lo2) {
while (lo2 < hi2) {
dst[k++] = a2[lo2++];
}
}
}
// [byte]
/**
* Sorts the specified range of the array using
* counting sort or insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(byte[] a, int low, int high) {
if (high - low > MIN_BYTE_COUNTING_SORT_SIZE) {
countingSort(a, low, high);
} else {
insertionSort(a, low, high);
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(byte[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
byte ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* The number of distinct byte values.
*/
private static final int NUM_BYTE_VALUES = 1 << 8;
/**
* Max index of byte counter.
*/
private static final int MAX_BYTE_INDEX = Byte.MAX_VALUE + NUM_BYTE_VALUES + 1;
/**
* Sorts the specified range of the array using counting sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void countingSort(byte[] a, int low, int high) {
int[] count = new int[NUM_BYTE_VALUES];
/*
* Compute a histogram with the number of each values.
*/
for (int i = high; i > low; ++count[a[--i] & 0xFF]);
/*
* Place values on their final positions.
*/
if (high - low > NUM_BYTE_VALUES) {
for (int i = MAX_BYTE_INDEX; --i > Byte.MAX_VALUE; ) {
int value = i & 0xFF;
for (low = high - count[value]; high > low;
a[--high] = (byte) value
);
}
} else {
for (int i = MAX_BYTE_INDEX; high > low; ) {
while (count[--i & 0xFF] == 0);
int value = i & 0xFF;
int c = count[value];
do {
a[--high] = (byte) value;
} while (--c > 0);
}
}
}
// [char]
/**
* Sorts the specified range of the array using
* counting sort or Dual-Pivot Quicksort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(char[] a, int low, int high) {
if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) {
countingSort(a, low, high);
} else {
sort(a, 0, low, high);
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(char[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Switch to counting sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
countingSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
char a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { char t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { char t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { char t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
char pivot1 = a[e1];
char pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
char ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively,
* excluding known pivots.
*/
sort(a, bits | 1, lower + 1, upper);
sort(a, bits | 1, upper + 1, high);
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
char pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
char ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part, excluding known pivot.
* All elements from the central part are
* equal and therefore already sorted.
*/
sort(a, bits | 1, upper, high);
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(char[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
char ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* The number of distinct char values.
*/
private static final int NUM_CHAR_VALUES = 1 << 16;
/**
* Sorts the specified range of the array using counting sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void countingSort(char[] a, int low, int high) {
int[] count = new int[NUM_CHAR_VALUES];
/*
* Compute a histogram with the number of each values.
*/
for (int i = high; i > low; ++count[a[--i]]);
/*
* Place values on their final positions.
*/
if (high - low > NUM_CHAR_VALUES) {
for (int i = NUM_CHAR_VALUES; i > 0; ) {
for (low = high - count[--i]; high > low;
a[--high] = (char) i
);
}
} else {
for (int i = NUM_CHAR_VALUES; high > low; ) {
while (count[--i] == 0);
int c = count[i];
do {
a[--high] = (char) i;
} while (--c > 0);
}
}
}
// [short]
/**
* Sorts the specified range of the array using
* counting sort or Dual-Pivot Quicksort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(short[] a, int low, int high) {
if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) {
countingSort(a, low, high);
} else {
sort(a, 0, low, high);
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(short[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Switch to counting sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
countingSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
short a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { short t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { short t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { short t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
short pivot1 = a[e1];
short pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
short ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively,
* excluding known pivots.
*/
sort(a, bits | 1, lower + 1, upper);
sort(a, bits | 1, upper + 1, high);
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
short pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
short ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part, excluding known pivot.
* All elements from the central part are
* equal and therefore already sorted.
*/
sort(a, bits | 1, upper, high);
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(short[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
short ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* The number of distinct short values.
*/
private static final int NUM_SHORT_VALUES = 1 << 16;
/**
* Max index of short counter.
*/
private static final int MAX_SHORT_INDEX = Short.MAX_VALUE + NUM_SHORT_VALUES + 1;
/**
* Sorts the specified range of the array using counting sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void countingSort(short[] a, int low, int high) {
int[] count = new int[NUM_SHORT_VALUES];
/*
* Compute a histogram with the number of each values.
*/
for (int i = high; i > low; ++count[a[--i] & 0xFFFF]);
/*
* Place values on their final positions.
*/
if (high - low > NUM_SHORT_VALUES) {
for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) {
int value = i & 0xFFFF;
for (low = high - count[value]; high > low;
a[--high] = (short) value
);
}
} else {
for (int i = MAX_SHORT_INDEX; high > low; ) {
while (count[--i & 0xFFFF] == 0);
int value = i & 0xFFFF;
int c = count[value];
do {
a[--high] = (short) value;
} while (--c > 0);
}
}
}
// [float]
/**
* Sorts the specified range of the array using parallel merge
* sort and/or Dual-Pivot Quicksort.
*
* To balance the faster splitting and parallelism of merge sort
* with the faster element partitioning of Quicksort, ranges are
* subdivided in tiers such that, if there is enough parallelism,
* the four-way parallel merge is started, still ensuring enough
* parallelism to process the partitions.
*
* @param a the array to be sorted
* @param parallelism the parallelism level
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(float[] a, int parallelism, int low, int high) {
/*
* Phase 1. Count the number of negative zero -0.0f,
* turn them into positive zero, and move all NaNs
* to the end of the array.
*/
int numNegativeZero = 0;
for (int k = high; k > low; ) {
float ak = a[--k];
if (ak == 0.0f && Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
numNegativeZero += 1;
a[k] = 0.0f;
} else if (ak != ak) { // ak is NaN
a[k] = a[--high];
a[high] = ak;
}
}
/*
* Phase 2. Sort everything except NaNs,
* which are already in place.
*/
int size = high - low;
if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
int depth = getDepth(parallelism, size >> 12);
float[] b = depth == 0 ? null : new float[size];
new Sorter(null, a, b, low, size, low, depth).invoke();
} else {
sort(null, a, 0, low, high);
}
/*
* Phase 3. Turn positive zero 0.0f
* back into negative zero -0.0f.
*/
if (++numNegativeZero == 1) {
return;
}
/*
* Find the position one less than
* the index of the first zero.
*/
while (low <= high) {
int middle = (low + high) >>> 1;
if (a[middle] < 0) {
low = middle + 1;
} else {
high = middle - 1;
}
}
/*
* Replace the required number of 0.0f by -0.0f.
*/
while (--numNegativeZero > 0) {
a[++high] = -0.0f;
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(Sorter sorter, float[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Run mixed insertion sort on small non-leftmost parts.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Check if the whole array or large non-leftmost
* parts are nearly sorted and then merge runs.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* Switch to heap sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
float a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { float t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { float t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { float t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
float pivot1 = a[e1];
float pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
float ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively (possibly in parallel),
* excluding known pivots.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, lower + 1, upper);
sorter.forkSorter(bits | 1, upper + 1, high);
} else {
sort(sorter, a, bits | 1, lower + 1, upper);
sort(sorter, a, bits | 1, upper + 1, high);
}
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
float pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
float ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part (possibly in parallel), excluding
* known pivot. All elements from the central part are
* equal and therefore already sorted.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, upper, high);
} else {
sort(sorter, a, bits | 1, upper, high);
}
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using mixed insertion sort.
*
* Mixed insertion sort is combination of simple insertion sort,
* pin insertion sort and pair insertion sort.
*
* In the context of Dual-Pivot Quicksort, the pivot element
* from the left part plays the role of sentinel, because it
* is less than any elements from the given part. Therefore,
* expensive check of the left range can be skipped on each
* iteration unless it is the leftmost call.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param end the index of the last element for simple insertion sort
* @param high the index of the last element, exclusive, to be sorted
*/
private static void mixedInsertionSort(float[] a, int low, int end, int high) {
if (end == high) {
/*
* Invoke simple insertion sort on tiny array.
*/
for (int i; ++low < end; ) {
float ai = a[i = low];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
} else {
/*
* Start with pin insertion sort on small part.
*
* Pin insertion sort is extended simple insertion sort.
* The main idea of this sort is to put elements larger
* than an element called pin to the end of array (the
* proper area for such elements). It avoids expensive
* movements of these elements through the whole array.
*/
float pin = a[end];
for (int i, p = high; ++low < end; ) {
float ai = a[i = low];
if (ai < a[i - 1]) { // Small element
/*
* Insert small element into sorted part.
*/
a[i] = a[--i];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
} else if (p > i && ai > pin) { // Large element
/*
* Find element smaller than pin.
*/
while (a[--p] > pin);
/*
* Swap it with large element.
*/
if (p > i) {
ai = a[p];
a[p] = a[i];
}
/*
* Insert small element into sorted part.
*/
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
/*
* Continue with pair insertion sort on remain part.
*/
for (int i; low < high; ++low) {
float a1 = a[i = low], a2 = a[++low];
/*
* Insert two elements per iteration: at first, insert the
* larger element and then insert the smaller element, but
* from the position where the larger element was inserted.
*/
if (a1 > a2) {
while (a1 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a1;
while (a2 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a2;
} else if (a1 < a[i - 1]) {
while (a2 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a2;
while (a1 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a1;
}
}
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(float[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
float ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* Sorts the specified range of the array using heap sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void heapSort(float[] a, int low, int high) {
for (int k = (low + high) >>> 1; k > low; ) {
pushDown(a, --k, a[k], low, high);
}
while (--high > low) {
float max = a[low];
pushDown(a, low, a[high], low, high);
a[high] = max;
}
}
/**
* Pushes specified element down during heap sort.
*
* @param a the given array
* @param p the start index
* @param value the given element
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void pushDown(float[] a, int p, float value, int low, int high) {
for (int k ;; a[p] = a[p = k]) {
k = (p << 1) - low + 2; // Index of the right child
if (k > high) {
break;
}
if (k == high || a[k] < a[k - 1]) {
--k;
}
if (a[k] <= value) {
break;
}
}
a[p] = value;
}
/**
* Tries to sort the specified range of the array.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param low the index of the first element to be sorted
* @param size the array size
* @return true if finally sorted, false otherwise
*/
private static boolean tryMergeRuns(Sorter sorter, float[] a, int low, int size) {
/*
* The run array is constructed only if initial runs are
* long enough to continue, run[i] then holds start index
* of the i-th sequence of elements in non-descending order.
*/
int[] run = null;
int high = low + size;
int count = 1, last = low;
/*
* Identify all possible runs.
*/
for (int k = low + 1; k < high; ) {
/*
* Find the end index of the current run.
*/
if (a[k - 1] < a[k]) {
// Identify ascending sequence
while (++k < high && a[k - 1] <= a[k]);
} else if (a[k - 1] > a[k]) {
// Identify descending sequence
while (++k < high && a[k - 1] >= a[k]);
// Reverse into ascending order
for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
float ai = a[i]; a[i] = a[j]; a[j] = ai;
}
} else { // Identify constant sequence
for (float ak = a[k]; ++k < high && ak == a[k]; );
if (k < high) {
continue;
}
}
/*
* Check special cases.
*/
if (run == null) {
if (k == high) {
/*
* The array is monotonous sequence,
* and therefore already sorted.
*/
return true;
}
if (k - low < MIN_FIRST_RUN_SIZE) {
/*
* The first run is too small
* to proceed with scanning.
*/
return false;
}
run = new int[((size >> 10) | 0x7F) & 0x3FF];
run[0] = low;
} else if (a[last - 1] > a[last]) {
if (count > (k - low) >> MIN_FIRST_RUNS_FACTOR) {
/*
* The first runs are not long
* enough to continue scanning.
*/
return false;
}
if (++count == MAX_RUN_CAPACITY) {
/*
* Array is not highly structured.
*/
return false;
}
if (count == run.length) {
/*
* Increase capacity of index array.
*/
run = Arrays.copyOf(run, count << 1);
}
}
run[count] = (last = k);
}
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
float[] b; int offset = low;
if (sorter == null || (b = (float[]) sorter.b) == null) {
b = new float[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
}
/**
* Merges the specified runs.
*
* @param a the source array
* @param b the temporary buffer used in merging
* @param offset the start index in the source, inclusive
* @param aim specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)
* @param parallel indicates whether merging is performed in parallel
* @param run the start indexes of the runs, inclusive
* @param lo the start index of the first run, inclusive
* @param hi the start index of the last run, inclusive
* @return the destination where runs are merged
*/
private static float[] mergeRuns(float[] a, float[] b, int offset,
int aim, boolean parallel, int[] run, int lo, int hi) {
if (hi - lo == 1) {
if (aim >= 0) {
return a;
}
for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
b[--j] = a[--i]
);
return b;
}
/*
* Split into approximately equal parts.
*/
int mi = lo, rmi = (run[lo] + run[hi]) >>> 1;
while (run[++mi + 1] <= rmi);
/*
* Merge the left and right parts.
*/
float[] a1, a2;
if (parallel && hi - lo > MIN_RUN_COUNT) {
RunMerger merger = new RunMerger(a, b, offset, 0, run, mi, hi).forkMe();
a1 = mergeRuns(a, b, offset, -aim, true, run, lo, mi);
a2 = (float[]) merger.getDestination();
} else {
a1 = mergeRuns(a, b, offset, -aim, false, run, lo, mi);
a2 = mergeRuns(a, b, offset, 0, false, run, mi, hi);
}
float[] dst = a1 == a ? b : a;
int k = a1 == a ? run[lo] - offset : run[lo];
int lo1 = a1 == b ? run[lo] - offset : run[lo];
int hi1 = a1 == b ? run[mi] - offset : run[mi];
int lo2 = a2 == b ? run[mi] - offset : run[mi];
int hi2 = a2 == b ? run[hi] - offset : run[hi];
if (parallel) {
new Merger(null, dst, k, a1, lo1, hi1, a2, lo2, hi2).invoke();
} else {
mergeParts(null, dst, k, a1, lo1, hi1, a2, lo2, hi2);
}
return dst;
}
/**
* Merges the sorted parts.
*
* @param merger parallel context
* @param dst the destination where parts are merged
* @param k the start index of the destination, inclusive
* @param a1 the first part
* @param lo1 the start index of the first part, inclusive
* @param hi1 the end index of the first part, exclusive
* @param a2 the second part
* @param lo2 the start index of the second part, inclusive
* @param hi2 the end index of the second part, exclusive
*/
private static void mergeParts(Merger merger, float[] dst, int k,
float[] a1, int lo1, int hi1, float[] a2, int lo2, int hi2) {
if (merger != null && a1 == a2) {
while (true) {
/*
* The first part must be larger.
*/
if (hi1 - lo1 < hi2 - lo2) {
int lo = lo1; lo1 = lo2; lo2 = lo;
int hi = hi1; hi1 = hi2; hi2 = hi;
}
/*
* Small parts will be merged sequentially.
*/
if (hi1 - lo1 < MIN_PARALLEL_MERGE_PARTS_SIZE) {
break;
}
/*
* Find the median of the larger part.
*/
int mi1 = (lo1 + hi1) >>> 1;
float key = a1[mi1];
int mi2 = hi2;
/*
* Partition the smaller part.
*/
for (int loo = lo2; loo < mi2; ) {
int t = (loo + mi2) >>> 1;
if (key > a2[t]) {
loo = t + 1;
} else {
mi2 = t;
}
}
int d = mi2 - lo2 + mi1 - lo1;
/*
* Merge the right sub-parts in parallel.
*/
merger.forkMerger(dst, k + d, a1, mi1, hi1, a2, mi2, hi2);
/*
* Process the sub-left parts.
*/
hi1 = mi1;
hi2 = mi2;
}
}
/*
* Merge small parts sequentially.
*/
while (lo1 < hi1 && lo2 < hi2) {
dst[k++] = a1[lo1] < a2[lo2] ? a1[lo1++] : a2[lo2++];
}
if (dst != a1 || k < lo1) {
while (lo1 < hi1) {
dst[k++] = a1[lo1++];
}
}
if (dst != a2 || k < lo2) {
while (lo2 < hi2) {
dst[k++] = a2[lo2++];
}
}
}
// [double]
/**
* Sorts the specified range of the array using parallel merge
* sort and/or Dual-Pivot Quicksort.
*
* To balance the faster splitting and parallelism of merge sort
* with the faster element partitioning of Quicksort, ranges are
* subdivided in tiers such that, if there is enough parallelism,
* the four-way parallel merge is started, still ensuring enough
* parallelism to process the partitions.
*
* @param a the array to be sorted
* @param parallelism the parallelism level
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(double[] a, int parallelism, int low, int high) {
/*
* Phase 1. Count the number of negative zero -0.0d,
* turn them into positive zero, and move all NaNs
* to the end of the array.
*/
int numNegativeZero = 0;
for (int k = high; k > low; ) {
double ak = a[--k];
if (ak == 0.0d && Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
numNegativeZero += 1;
a[k] = 0.0d;
} else if (ak != ak) { // ak is NaN
a[k] = a[--high];
a[high] = ak;
}
}
/*
* Phase 2. Sort everything except NaNs,
* which are already in place.
*/
int size = high - low;
if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
int depth = getDepth(parallelism, size >> 12);
double[] b = depth == 0 ? null : new double[size];
new Sorter(null, a, b, low, size, low, depth).invoke();
} else {
sort(null, a, 0, low, high);
}
/*
* Phase 3. Turn positive zero 0.0d
* back into negative zero -0.0d.
*/
if (++numNegativeZero == 1) {
return;
}
/*
* Find the position one less than
* the index of the first zero.
*/
while (low <= high) {
int middle = (low + high) >>> 1;
if (a[middle] < 0) {
low = middle + 1;
} else {
high = middle - 1;
}
}
/*
* Replace the required number of 0.0d by -0.0d.
*/
while (--numNegativeZero > 0) {
a[++high] = -0.0d;
}
}
/**
* Sorts the specified array using the Dual-Pivot Quicksort and/or
* other sorts in special-cases, possibly with parallel partitions.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param bits the combination of recursion depth and bit flag, where
* the right bit "0" indicates that array is the leftmost part
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
static void sort(Sorter sorter, double[] a, int bits, int low, int high) {
while (true) {
int end = high - 1, size = high - low;
/*
* Run mixed insertion sort on small non-leftmost parts.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Check if the whole array or large non-leftmost
* parts are nearly sorted and then merge runs.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* Switch to heap sort if execution
* time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
/*
* Use an inexpensive approximation of the golden ratio
* to select five sample elements and determine pivots.
*/
int step = (size >> 3) * 3 + 3;
/*
* Five elements around (and including) the central element
* will be used for pivot selection as described below. The
* unequal choice of spacing these elements was empirically
* determined to work well on a wide variety of inputs.
*/
int e1 = low + step;
int e5 = end - step;
int e3 = (e1 + e5) >>> 1;
int e2 = (e1 + e3) >>> 1;
int e4 = (e3 + e5) >>> 1;
double a3 = a[e3];
/*
* Sort these elements in place by the combination
* of 4-element sorting network and insertion sort.
*
* 5 ------o-----------o------------
* | |
* 4 ------|-----o-----o-----o------
* | | |
* 2 ------o-----|-----o-----o------
* | |
* 1 ------------o-----o------------
*/
if (a[e5] < a[e2]) { double t = a[e5]; a[e5] = a[e2]; a[e2] = t; }
if (a[e4] < a[e1]) { double t = a[e4]; a[e4] = a[e1]; a[e1] = t; }
if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t; }
if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
if (a[e4] < a[e2]) { double t = a[e4]; a[e4] = a[e2]; a[e2] = t; }
if (a3 < a[e2]) {
if (a3 < a[e1]) {
a[e3] = a[e2]; a[e2] = a[e1]; a[e1] = a3;
} else {
a[e3] = a[e2]; a[e2] = a3;
}
} else if (a3 > a[e4]) {
if (a3 > a[e5]) {
a[e3] = a[e4]; a[e4] = a[e5]; a[e5] = a3;
} else {
a[e3] = a[e4]; a[e4] = a3;
}
}
// Pointers
int lower = low; // The index of the last element of the left part
int upper = end; // The index of the first element of the right part
/*
* Partitioning with 2 pivots in case of different elements.
*/
if (a[e1] < a[e2] && a[e2] < a[e3] && a[e3] < a[e4] && a[e4] < a[e5]) {
/*
* Use the first and fifth of the five sorted elements as
* the pivots. These values are inexpensive approximation
* of tertiles. Note, that pivot1 < pivot2.
*/
double pivot1 = a[e1];
double pivot2 = a[e5];
/*
* The first and the last elements to be sorted are moved
* to the locations formerly occupied by the pivots. When
* partitioning is completed, the pivots are swapped back
* into their final positions, and excluded from the next
* subsequent sorting.
*/
a[e1] = a[lower];
a[e5] = a[upper];
/*
* Skip elements, which are less or greater than the pivots.
*/
while (a[++lower] < pivot1);
while (a[--upper] > pivot2);
/*
* Backward 3-interval partitioning
*
* left part central part right part
* +------------------------------------------------------------+
* | < pivot1 | ? | pivot1 <= && <= pivot2 | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot1
* pivot1 <= all in (k, upper) <= pivot2
* all in [upper, end) > pivot2
*
* Pointer k is the last index of ?-part
*/
for (int unused = --lower, k = ++upper; --k > lower; ) {
double ak = a[k];
if (ak < pivot1) { // Move a[k] to the left side
while (lower < k) {
if (a[++lower] >= pivot1) {
if (a[lower] > pivot2) {
a[k] = a[--upper];
a[upper] = a[lower];
} else {
a[k] = a[lower];
}
a[lower] = ak;
break;
}
}
} else if (ak > pivot2) { // Move a[k] to the right side
a[k] = a[--upper];
a[upper] = ak;
}
}
/*
* Swap the pivots into their final positions.
*/
a[low] = a[lower]; a[lower] = pivot1;
a[end] = a[upper]; a[upper] = pivot2;
/*
* Sort non-left parts recursively (possibly in parallel),
* excluding known pivots.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, lower + 1, upper);
sorter.forkSorter(bits | 1, upper + 1, high);
} else {
sort(sorter, a, bits | 1, lower + 1, upper);
sort(sorter, a, bits | 1, upper + 1, high);
}
} else { // Use single pivot in case of many equal elements
/*
* Use the third of the five sorted elements as the pivot.
* This value is inexpensive approximation of the median.
*/
double pivot = a[e3];
/*
* The first element to be sorted is moved to the
* location formerly occupied by the pivot. After
* completion of partitioning the pivot is swapped
* back into its final position, and excluded from
* the next subsequent sorting.
*/
a[e3] = a[lower];
/*
* Traditional 3-way (Dutch National Flag) partitioning
*
* left part central part right part
* +------------------------------------------------------+
* | < pivot | ? | == pivot | > pivot |
* +------------------------------------------------------+
* ^ ^ ^
* | | |
* lower k upper
*
* Invariants:
*
* all in (low, lower] < pivot
* all in (k, upper) == pivot
* all in [upper, end] > pivot
*
* Pointer k is the last index of ?-part
*/
for (int k = ++upper; --k > lower; ) {
double ak = a[k];
if (ak != pivot) {
a[k] = pivot;
if (ak < pivot) { // Move a[k] to the left side
while (a[++lower] < pivot);
if (a[lower] > pivot) {
a[--upper] = a[lower];
}
a[lower] = ak;
} else { // ak > pivot - Move a[k] to the right side
a[--upper] = ak;
}
}
}
/*
* Swap the pivot into its final position.
*/
a[low] = a[lower]; a[lower] = pivot;
/*
* Sort the right part (possibly in parallel), excluding
* known pivot. All elements from the central part are
* equal and therefore already sorted.
*/
if (size > MIN_PARALLEL_SORT_SIZE && sorter != null) {
sorter.forkSorter(bits | 1, upper, high);
} else {
sort(sorter, a, bits | 1, upper, high);
}
}
high = lower; // Iterate along the left part
}
}
/**
* Sorts the specified range of the array using mixed insertion sort.
*
* Mixed insertion sort is combination of simple insertion sort,
* pin insertion sort and pair insertion sort.
*
* In the context of Dual-Pivot Quicksort, the pivot element
* from the left part plays the role of sentinel, because it
* is less than any elements from the given part. Therefore,
* expensive check of the left range can be skipped on each
* iteration unless it is the leftmost call.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param end the index of the last element for simple insertion sort
* @param high the index of the last element, exclusive, to be sorted
*/
private static void mixedInsertionSort(double[] a, int low, int end, int high) {
if (end == high) {
/*
* Invoke simple insertion sort on tiny array.
*/
for (int i; ++low < end; ) {
double ai = a[i = low];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
} else {
/*
* Start with pin insertion sort on small part.
*
* Pin insertion sort is extended simple insertion sort.
* The main idea of this sort is to put elements larger
* than an element called pin to the end of array (the
* proper area for such elements). It avoids expensive
* movements of these elements through the whole array.
*/
double pin = a[end];
for (int i, p = high; ++low < end; ) {
double ai = a[i = low];
if (ai < a[i - 1]) { // Small element
/*
* Insert small element into sorted part.
*/
a[i] = a[--i];
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
} else if (p > i && ai > pin) { // Large element
/*
* Find element smaller than pin.
*/
while (a[--p] > pin);
/*
* Swap it with large element.
*/
if (p > i) {
ai = a[p];
a[p] = a[i];
}
/*
* Insert small element into sorted part.
*/
while (ai < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
/*
* Continue with pair insertion sort on remain part.
*/
for (int i; low < high; ++low) {
double a1 = a[i = low], a2 = a[++low];
/*
* Insert two elements per iteration: at first, insert the
* larger element and then insert the smaller element, but
* from the position where the larger element was inserted.
*/
if (a1 > a2) {
while (a1 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a1;
while (a2 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a2;
} else if (a1 < a[i - 1]) {
while (a2 < a[--i]) {
a[i + 2] = a[i];
}
a[++i + 1] = a2;
while (a1 < a[--i]) {
a[i + 1] = a[i];
}
a[i + 1] = a1;
}
}
}
}
/**
* Sorts the specified range of the array using insertion sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void insertionSort(double[] a, int low, int high) {
for (int i, k = low; ++k < high; ) {
double ai = a[i = k];
if (ai < a[i - 1]) {
while (--i >= low && ai < a[i]) {
a[i + 1] = a[i];
}
a[i + 1] = ai;
}
}
}
/**
* Sorts the specified range of the array using heap sort.
*
* @param a the array to be sorted
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void heapSort(double[] a, int low, int high) {
for (int k = (low + high) >>> 1; k > low; ) {
pushDown(a, --k, a[k], low, high);
}
while (--high > low) {
double max = a[low];
pushDown(a, low, a[high], low, high);
a[high] = max;
}
}
/**
* Pushes specified element down during heap sort.
*
* @param a the given array
* @param p the start index
* @param value the given element
* @param low the index of the first element, inclusive, to be sorted
* @param high the index of the last element, exclusive, to be sorted
*/
private static void pushDown(double[] a, int p, double value, int low, int high) {
for (int k ;; a[p] = a[p = k]) {
k = (p << 1) - low + 2; // Index of the right child
if (k > high) {
break;
}
if (k == high || a[k] < a[k - 1]) {
--k;
}
if (a[k] <= value) {
break;
}
}
a[p] = value;
}
/**
* Tries to sort the specified range of the array.
*
* @param sorter parallel context
* @param a the array to be sorted
* @param low the index of the first element to be sorted
* @param size the array size
* @return true if finally sorted, false otherwise
*/
private static boolean tryMergeRuns(Sorter sorter, double[] a, int low, int size) {
/*
* The run array is constructed only if initial runs are
* long enough to continue, run[i] then holds start index
* of the i-th sequence of elements in non-descending order.
*/
int[] run = null;
int high = low + size;
int count = 1, last = low;
/*
* Identify all possible runs.
*/
for (int k = low + 1; k < high; ) {
/*
* Find the end index of the current run.
*/
if (a[k - 1] < a[k]) {
// Identify ascending sequence
while (++k < high && a[k - 1] <= a[k]);
} else if (a[k - 1] > a[k]) {
// Identify descending sequence
while (++k < high && a[k - 1] >= a[k]);
// Reverse into ascending order
for (int i = last - 1, j = k; ++i < --j && a[i] > a[j]; ) {
double ai = a[i]; a[i] = a[j]; a[j] = ai;
}
} else { // Identify constant sequence
for (double ak = a[k]; ++k < high && ak == a[k]; );
if (k < high) {
continue;
}
}
/*
* Check special cases.
*/
if (run == null) {
if (k == high) {
/*
* The array is monotonous sequence,
* and therefore already sorted.
*/
return true;
}
if (k - low < MIN_FIRST_RUN_SIZE) {
/*
* The first run is too small
* to proceed with scanning.
*/
return false;
}
run = new int[((size >> 10) | 0x7F) & 0x3FF];
run[0] = low;
} else if (a[last - 1] > a[last]) {
if (count > (k - low) >> MIN_FIRST_RUNS_FACTOR) {
/*
* The first runs are not long
* enough to continue scanning.
*/
return false;
}
if (++count == MAX_RUN_CAPACITY) {
/*
* Array is not highly structured.
*/
return false;
}
if (count == run.length) {
/*
* Increase capacity of index array.
*/
run = Arrays.copyOf(run, count << 1);
}
}
run[count] = (last = k);
}
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
double[] b; int offset = low;
if (sorter == null || (b = (double[]) sorter.b) == null) {
b = new double[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
}
/**
* Merges the specified runs.
*
* @param a the source array
* @param b the temporary buffer used in merging
* @param offset the start index in the source, inclusive
* @param aim specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)
* @param parallel indicates whether merging is performed in parallel
* @param run the start indexes of the runs, inclusive
* @param lo the start index of the first run, inclusive
* @param hi the start index of the last run, inclusive
* @return the destination where runs are merged
*/
private static double[] mergeRuns(double[] a, double[] b, int offset,
int aim, boolean parallel, int[] run, int lo, int hi) {
if (hi - lo == 1) {
if (aim >= 0) {
return a;
}
for (int i = run[hi], j = i - offset, low = run[lo]; i > low;
b[--j] = a[--i]
);
return b;
}
/*
* Split into approximately equal parts.
*/
int mi = lo, rmi = (run[lo] + run[hi]) >>> 1;
while (run[++mi + 1] <= rmi);
/*
* Merge the left and right parts.
*/
double[] a1, a2;
if (parallel && hi - lo > MIN_RUN_COUNT) {
RunMerger merger = new RunMerger(a, b, offset, 0, run, mi, hi).forkMe();
a1 = mergeRuns(a, b, offset, -aim, true, run, lo, mi);
a2 = (double[]) merger.getDestination();
} else {
a1 = mergeRuns(a, b, offset, -aim, false, run, lo, mi);
a2 = mergeRuns(a, b, offset, 0, false, run, mi, hi);
}
double[] dst = a1 == a ? b : a;
int k = a1 == a ? run[lo] - offset : run[lo];
int lo1 = a1 == b ? run[lo] - offset : run[lo];
int hi1 = a1 == b ? run[mi] - offset : run[mi];
int lo2 = a2 == b ? run[mi] - offset : run[mi];
int hi2 = a2 == b ? run[hi] - offset : run[hi];
if (parallel) {
new Merger(null, dst, k, a1, lo1, hi1, a2, lo2, hi2).invoke();
} else {
mergeParts(null, dst, k, a1, lo1, hi1, a2, lo2, hi2);
}
return dst;
}
/**
* Merges the sorted parts.
*
* @param merger parallel context
* @param dst the destination where parts are merged
* @param k the start index of the destination, inclusive
* @param a1 the first part
* @param lo1 the start index of the first part, inclusive
* @param hi1 the end index of the first part, exclusive
* @param a2 the second part
* @param lo2 the start index of the second part, inclusive
* @param hi2 the end index of the second part, exclusive
*/
private static void mergeParts(Merger merger, double[] dst, int k,
double[] a1, int lo1, int hi1, double[] a2, int lo2, int hi2) {
if (merger != null && a1 == a2) {
while (true) {
/*
* The first part must be larger.
*/
if (hi1 - lo1 < hi2 - lo2) {
int lo = lo1; lo1 = lo2; lo2 = lo;
int hi = hi1; hi1 = hi2; hi2 = hi;
}
/*
* Small parts will be merged sequentially.
*/
if (hi1 - lo1 < MIN_PARALLEL_MERGE_PARTS_SIZE) {
break;
}
/*
* Find the median of the larger part.
*/
int mi1 = (lo1 + hi1) >>> 1;
double key = a1[mi1];
int mi2 = hi2;
/*
* Partition the smaller part.
*/
for (int loo = lo2; loo < mi2; ) {
int t = (loo + mi2) >>> 1;
if (key > a2[t]) {
loo = t + 1;
} else {
mi2 = t;
}
}
int d = mi2 - lo2 + mi1 - lo1;
/*
* Merge the right sub-parts in parallel.
*/
merger.forkMerger(dst, k + d, a1, mi1, hi1, a2, mi2, hi2);
/*
* Process the sub-left parts.
*/
hi1 = mi1;
hi2 = mi2;
}
}
/*
* Merge small parts sequentially.
*/
while (lo1 < hi1 && lo2 < hi2) {
dst[k++] = a1[lo1] < a2[lo2] ? a1[lo1++] : a2[lo2++];
}
if (dst != a1 || k < lo1) {
while (lo1 < hi1) {
dst[k++] = a1[lo1++];
}
}
if (dst != a2 || k < lo2) {
while (lo2 < hi2) {
dst[k++] = a2[lo2++];
}
}
}
// [class]
/**
* This class implements parallel sorting.
*/
private static final class Sorter extends CountedCompleter<Void> {
private static final long serialVersionUID = 20180818L;
private final Object a, b;
private final int low, size, offset, depth;
private Sorter(CountedCompleter<?> parent,
Object a, Object b, int low, int size, int offset, int depth) {
super(parent);
this.a = a;
this.b = b;
this.low = low;
this.size = size;
this.offset = offset;
this.depth = depth;
}
@Override
public final void compute() {
if (depth < 0) {
setPendingCount(2);
int half = size >> 1;
new Sorter(this, b, a, low, half, offset, depth + 1).fork();
new Sorter(this, b, a, low + half, size - half, offset, depth + 1).compute();
} else {
if (a instanceof int[]) {
sort(this, (int[]) a, depth, low, low + size);
} else if (a instanceof long[]) {
sort(this, (long[]) a, depth, low, low + size);
} else if (a instanceof float[]) {
sort(this, (float[]) a, depth, low, low + size);
} else if (a instanceof double[]) {
sort(this, (double[]) a, depth, low, low + size);
} else {
throw new IllegalArgumentException(
"Unknown type of array: " + a.getClass().getName());
}
}
tryComplete();
}
@Override
public final void onCompletion(CountedCompleter<?> caller) {
if (depth < 0) {
int mi = low + (size >> 1);
boolean src = (depth & 1) == 0;
new Merger(null,
a,
src ? low : low - offset,
b,
src ? low - offset : low,
src ? mi - offset : mi,
b,
src ? mi - offset : mi,
src ? low + size - offset : low + size
).invoke();
}
}
private void forkSorter(int depth, int low, int high) {
addToPendingCount(1);
Object a = this.a; // Use local variable for performance
new Sorter(this, a, b, low, high - low, offset, depth).fork();
}
}
/**
* This class implements parallel merging.
*/
private static final class Merger extends CountedCompleter<Void> {
private static final long serialVersionUID = 20180818L;
private final Object dst, a1, a2;
private final int k, lo1, hi1, lo2, hi2;
private Merger(CountedCompleter<?> parent, Object dst, int k,
Object a1, int lo1, int hi1, Object a2, int lo2, int hi2) {
super(parent);
this.dst = dst;
this.k = k;
this.a1 = a1;
this.lo1 = lo1;
this.hi1 = hi1;
this.a2 = a2;
this.lo2 = lo2;
this.hi2 = hi2;
}
@Override
public final void compute() {
if (dst instanceof int[]) {
mergeParts(this, (int[]) dst, k,
(int[]) a1, lo1, hi1, (int[]) a2, lo2, hi2);
} else if (dst instanceof long[]) {
mergeParts(this, (long[]) dst, k,
(long[]) a1, lo1, hi1, (long[]) a2, lo2, hi2);
} else if (dst instanceof float[]) {
mergeParts(this, (float[]) dst, k,
(float[]) a1, lo1, hi1, (float[]) a2, lo2, hi2);
} else if (dst instanceof double[]) {
mergeParts(this, (double[]) dst, k,
(double[]) a1, lo1, hi1, (double[]) a2, lo2, hi2);
} else {
throw new IllegalArgumentException(
"Unknown type of array: " + dst.getClass().getName());
}
propagateCompletion();
}
private void forkMerger(Object dst, int k,
Object a1, int lo1, int hi1, Object a2, int lo2, int hi2) {
addToPendingCount(1);
new Merger(this, dst, k, a1, lo1, hi1, a2, lo2, hi2).fork();
}
}
/**
* This class implements parallel merging of runs.
*/
private static final class RunMerger extends RecursiveTask<Object> {
private static final long serialVersionUID = 20180818L;
private final Object a, b;
private final int[] run;
private final int offset, aim, lo, hi;
private RunMerger(Object a, Object b, int offset,
int aim, int[] run, int lo, int hi) {
this.a = a;
this.b = b;
this.offset = offset;
this.aim = aim;
this.run = run;
this.lo = lo;
this.hi = hi;
}
@Override
protected final Object compute() {
if (a instanceof int[]) {
return mergeRuns((int[]) a, (int[]) b, offset, aim, true, run, lo, hi);
}
if (a instanceof long[]) {
return mergeRuns((long[]) a, (long[]) b, offset, aim, true, run, lo, hi);
}
if (a instanceof float[]) {
return mergeRuns((float[]) a, (float[]) b, offset, aim, true, run, lo, hi);
}
if (a instanceof double[]) {
return mergeRuns((double[]) a, (double[]) b, offset, aim, true, run, lo, hi);
}
throw new IllegalArgumentException(
"Unknown type of array: " + a.getClass().getName());
}
private RunMerger forkMe() {
fork();
return this;
}
private Object getDestination() {
join();
return getRawResult();
}
}
}