3909N/A * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. 1804N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1804N/A * This code is free software; you can redistribute it and/or modify it 1804N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 1804N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 1804N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1804N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1804N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1804N/A * version 2 for more details (a copy is included in the LICENSE file that 1804N/A * You should have received a copy of the GNU General Public License version 1804N/A * 2 along with this work; if not, write to the Free Software Foundation, 1804N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 1804N/A * This class implements the Dual-Pivot Quicksort algorithm by 2571N/A * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm 1804N/A * offers O(n log(n)) performance on many data sets that cause other 1804N/A * quicksorts to degrade to quadratic performance, and is typically 1804N/A * faster than traditional (one-pivot) Quicksort implementations. 1804N/A * @author Vladimir Yaroslavskiy 3506N/A * @version 2011.02.11 m765.827.12i:5\7pm 3501N/A * The maximum number of runs in merge sort. 3501N/A * The maximum length of run in merge sort. 3501N/A * If the length of an array to be sorted is less than this 3501N/A * constant, Quicksort is used in preference to merge sort. 1804N/A * If the length of an array to be sorted is less than this 1804N/A * constant, insertion sort is used in preference to Quicksort. 2930N/A * If the length of a byte array to be sorted is greater than this 2930N/A * constant, counting sort is used in preference to insertion sort. 1804N/A * If the length of a short or char array to be sorted is greater 1804N/A * than this constant, counting sort is used in preference to Quicksort. 2571N/A * Sorting methods for seven primitive types. 2930N/A * Sorts the specified array. 1867N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1867N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 2930N/A * @param a the array to be sorted 2930N/A * @param left the index of the first element, inclusive, to be sorted 2930N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted. 2930N/A * Sorts the specified array. 1867N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1867N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 3501N/A long[] t = a; a = b; b = t;
2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 2930N/A * @param a the array to be sorted 2930N/A * @param left the index of the first element, inclusive, to be sorted 2930N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted. 2930N/A * Sorts the specified array. 1867N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1867N/A * @param a the array to be sorted 2930N/A * @param left the index of the first element, inclusive, to be sorted 2930N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A // Use counting sort on large arrays 2930N/A }
else {
// Use Dual-Pivot Quicksort on small arrays 1867N/A /** The number of distinct short values. */ 3501N/A * Sorts the specified range of the array. 3501N/A * @param a the array to be sorted 3501N/A * @param left the index of the first element, inclusive, to be sorted 3501N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 3501N/A short[] t = a; a = b; b = t;
2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted. 2930N/A * Sorts the specified array. 1804N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1804N/A * @param a the array to be sorted 2930N/A * @param left the index of the first element, inclusive, to be sorted 2930N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A // Use counting sort on large arrays 2930N/A }
else {
// Use Dual-Pivot Quicksort on small arrays 1867N/A /** The number of distinct char values. */ 3501N/A * Sorts the specified range of the array. 3501N/A * @param a the array to be sorted 3501N/A * @param left the index of the first element, inclusive, to be sorted 3501N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 3501N/A char[] t = a; a = b; b = t;
2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted. 1867N/A /** The number of distinct byte values. */ 2930N/A * Sorts the specified array. 2930N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A // Use counting sort on large arrays 2930N/A }
else {
// Use insertion sort on small arrays 2930N/A * Sorts the specified array. 1867N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1867N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2571N/A * Phase 1: Move NaNs to the end of the array. 2571N/A * Phase 2: Sort everything except NaNs (which are already in place). 2571N/A * Phase 3: Place negative zeros before positive zeros. 2930N/A * Find the first zero, or first positive, or last negative element. 2571N/A * Skip the last negative value (if any) or all leading negative zeros. 2571N/A * Move negative zeros to the beginning of the sub-range. 2930N/A * +----------------------------------------------------+ 2930N/A * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | 2930N/A * +----------------------------------------------------+ 2571N/A * Pointer k is the first index of ?-part. 3501N/A * Sorts the specified range of the array. 3501N/A * @param a the array to be sorted 3501N/A * @param left the index of the first element, inclusive, to be sorted 3501N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 3501N/A float[] t = a; a = b; b = t;
2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted. 2930N/A * Sorts the specified array. 1867N/A * @param a the array to be sorted 2930N/A * Sorts the specified range of the array. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2571N/A * Phase 1: Move NaNs to the end of the array. 2571N/A * Phase 2: Sort everything except NaNs (which are already in place). 2571N/A * Phase 3: Place negative zeros before positive zeros. 2930N/A * Find the first zero, or first positive, or last negative element. 2571N/A * Skip the last negative value (if any) or all leading negative zeros. 2571N/A * Move negative zeros to the beginning of the sub-range. 2930N/A * +----------------------------------------------------+ 2930N/A * | < 0.0 | -0.0 | 0.0 | ? ( >= 0.0 ) | 2930N/A * +----------------------------------------------------+ 2571N/A * Pointer k is the first index of ?-part. 3501N/A * Sorts the specified range of the array. 3501N/A * @param a the array to be sorted 3501N/A * @param left the index of the first element, inclusive, to be sorted 3501N/A * @param right the index of the last element, inclusive, to be sorted 3501N/A // Use Quicksort on small arrays 3501N/A * Index run[i] is the start of i-th run 3501N/A * (ascending or descending sequence). 3501N/A // Check if the array is nearly sorted 3501N/A if (a[k] < a[k +
1]) {
// ascending 3501N/A }
else if (a[k] > a[k +
1]) {
// descending 3501N/A * The array is not highly structured, 3501N/A * use Quicksort instead of merge sort. 3501N/A }
else if (
count ==
1) {
// The array is already sorted 3501N/A * Create temporary array, which is used for merging. 3501N/A * Implementation note: variable "right" is increased by 1. 3501N/A double[] t = a; a = b; b = t;
2930N/A * Sorts the specified range of the array by Dual-Pivot Quicksort. 1804N/A * @param a the array to be sorted 1867N/A * @param left the index of the first element, inclusive, to be sorted 1867N/A * @param right the index of the last element, inclusive, to be sorted 2930N/A * @param leftmost indicates if this part is the leftmost in the range 3501N/A // Use insertion sort on tiny arrays 2930N/A * Traditional (without sentinel) insertion sort, 2930N/A * optimized for server VM, is used in case of 2930N/A * Skip the longest ascending sequence. 2930N/A * Every element from adjoining part plays the role 2930N/A * of sentinel, therefore this allows us to avoid the 2930N/A * left range check on each iteration. Moreover, we use 3501N/A * the more optimized algorithm, so called pair insertion 3501N/A * sort, which is faster (in the context of Quicksort) 3501N/A * than traditional implementation of insertion sort. 2571N/A // Inexpensive approximation of length / 7 2571N/A * Sort five evenly spaced elements around (and including) the 2571N/A * center element in the range. These elements will be used for 2571N/A * pivot selection as described below. The choice for spacing 2571N/A * these elements was empirically determined to work well on 2571N/A * a wide variety of inputs. 2571N/A // Sort these elements using insertion sort 3501N/A * Use the second and fourth of the five sorted elements as pivots. 3501N/A * These values are inexpensive approximations of the first and 3501N/A * second terciles of the array. Note that pivot1 <= pivot2. 2571N/A * The first and the last elements to be sorted are moved to the 2571N/A * locations formerly occupied by the pivots. When partitioning 2571N/A * is complete, the pivots are swapped back into their final 2571N/A * positions, and excluded from subsequent sorting. 2571N/A * Skip elements, which are less or greater than pivot values. 2571N/A * left part center part right part 2571N/A * +--------------------------------------------------------------+ 2571N/A * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 2571N/A * +--------------------------------------------------------------+ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 2571N/A * Pointer k is the first index of ?-part. 2930N/A * Here and below we use "a[i] = b; i++;" instead 2930N/A * of "a[i++] = b;" due to performance issue. 1961N/A }
else {
// pivot1 <= a[great] <= pivot2 2930N/A * Here and below we use "a[i] = b; i--;" instead 2930N/A * of "a[i--] = b;" due to performance issue. 2571N/A // Swap pivots into their final positions 2571N/A // Sort left and right parts recursively, excluding known pivots 2930N/A * If center part is too large (comprises > 4/7 of the array), 2571N/A * swap internal pivot values to ends. 2571N/A * Skip elements, which are equal to pivot values. 2571N/A * left part center part right part 2571N/A * +----------------------------------------------------------+ 2571N/A * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 2571N/A * +----------------------------------------------------------+ 2571N/A * all in (*, less) == pivot1 2571N/A * pivot1 < all in [less, k) < pivot2 2571N/A * all in (great, *) == pivot2 2571N/A * Pointer k is the first index of ?-part. 2571N/A * Even though a[great] equals to pivot1, the 2571N/A * assignment a[less] = pivot1 may be incorrect, 2571N/A * if a[great] and pivot1 are floating-point zeros 2571N/A * of different signs. Therefore in float and 2571N/A * double sorting methods we have to use more 2571N/A * accurate assignment a[less] = a[great]. 2571N/A }
else {
// pivot1 < a[great] < pivot2 2571N/A // Sort center part recursively 3501N/A }
else {
// Partitioning with one pivot 3501N/A * Use the third of the five sorted elements as pivot. 3501N/A * This value is inexpensive approximation of the median. 2930N/A * Partitioning degenerates to the traditional 3-way 2571N/A * (or "Dutch National Flag") schema: 2571N/A * left part center part right part 2571N/A * +-------------------------------------------------+ 2571N/A * | < pivot | == pivot | ? | > pivot | 2571N/A * +-------------------------------------------------+ 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 2571N/A * Pointer k is the first index of ?-part. 3501N/A }
else {
// a[k] > pivot - Move a[k] to right part 3501N/A }
else {
// a[great] == pivot 3501N/A * Even though a[great] equals to pivot, the 3501N/A * assignment a[k] = pivot may be incorrect, 3501N/A * if a[great] and pivot are floating-point 2571N/A * zeros of different signs. Therefore in float 2571N/A * and double sorting methods we have to use 2571N/A * more accurate assignment a[k] = a[great]. 2930N/A * Sort left and right parts recursively. 2930N/A * All elements from center part are equal 2930N/A * and, therefore, already sorted.