DualPivotQuicksort.java revision 1804
1804N/A * Copyright 2009 Sun Microsystems, Inc. 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 1804N/A * published by the Free Software Foundation. Sun designates this 1804N/A * particular file as subject to the "Classpath" exception as provided 1804N/A * by Sun 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. 1804N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1804N/A * CA 95054 USA or visit www.sun.com if you need additional information or 1804N/A * This class implements the Dual-Pivot Quicksort algorithm by 1804N/A * Vladimir Yaroslavskiy, Jon Bentley, and Joshua 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 1804N/A * @version 2009.10.22 m765.827.v4 1804N/A // Suppresses default constructor, ensuring non-instantiability. 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. 1804N/A * If the length of a byte array to be sorted is greater than 1804N/A * this constant, counting sort is used in preference to Quicksort. 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. 1804N/A * Sorting methods for the seven primitive types. 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A /** The number of distinct short values */ 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A // Use counting sort on huge arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values 1804N/A /** The number of distinct byte values */ 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A // Use counting sort on large arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values 1804N/A /** The number of distinct char values */ 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A // Use counting sort on huge arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values 1804N/A * Sorts the specified range of the array into ascending order. 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Use insertion sort on tiny arrays 1804N/A }
else {
// Use Dual-Pivot Quicksort on large arrays 1804N/A * Sorts the specified range of the array into ascending order 1804N/A * @param a the array to be sorted 1804N/A * @param left the index of the first element, inclusively, to be sorted 1804N/A * @param right the index of the last element, inclusively, to be sorted 1804N/A // Compute indices of five evenly spaced elements 1804N/A // Sort these elements in place using a 5-element sorting network 1804N/A * Use the second and fourth of the five sorted elements as pivots. 1804N/A * These values are inexpensive approximations of the first and 1804N/A * second terciles of the array. Note that pivot1 <= pivot2. 1804N/A * The pivots are stored in local variables, and the first and 1804N/A * the last of the sorted elements are moved to the locations 1804N/A * formerly occupied by the pivots. When partitioning is complete, 1804N/A * the pivots are swapped back into their final positions, and 1804N/A * excluded from subsequent sorting. 1804N/A * left part center part right part 1804N/A * ------------------------------------------------------------ 1804N/A * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ] 1804N/A * ------------------------------------------------------------ 1804N/A * all in (left, less) < pivot1 1804N/A * pivot1 <= all in [less, k) <= pivot2 1804N/A * all in (great, right) > pivot2 1804N/A * Pointer k is the first index of ?-part 1804N/A }
else {
// Pivots are equal 1804N/A * Partition degenerates to the traditional 3-way 1804N/A * (or "Dutch National Flag") partition: 1804N/A * left part center part right part 1804N/A * ------------------------------------------------- 1804N/A * [ < pivot | == pivot | ? | > pivot ] 1804N/A * ------------------------------------------------- 1804N/A * all in (left, less) < pivot 1804N/A * all in [less, k) == pivot 1804N/A * all in (great, right) > pivot 1804N/A * Pointer k is the first index of ?-part 1804N/A // Swap pivots into their final positions 1804N/A // Sort left and right parts recursively, excluding known pivot values 1804N/A * If pivot1 == pivot2, all elements from center 1804N/A * part are equal and, therefore, already sorted 1804N/A * If center part is too large (comprises > 5/6 of 1804N/A * the array), swap internal pivot values to ends 1804N/A // Sort center part recursively, excluding known pivot values