OpenJDK 27 · java.util.DualPivotQuicksort · APIdia, the JavaDoc alternative

Modifier and Type	Class and Description
private static class	DualPivotQuicksort.Merger This class implements parallel merging.
pack-priv static interface	DualPivotQuicksort.PartitionOperation<A> Represents a function that accepts the array and partitions the specified range of the array using the pivots provided.
private static class	DualPivotQuicksort.RunMerger This class implements parallel merging of runs.
private static class	DualPivotQuicksort.Sorter This class implements parallel sorting.
private static interface	DualPivotQuicksort.SortOperation<A> Represents a function that accepts the array and sorts the specified range of the array into ascending order.

Modifier and Type	Field and Description
private static final int	DELTA Threshold of mixed insertion sort is incremented by this value.
private static final int	MAX_BYTE_INDEX Max index of byte counter.
private static final int	MAX_INSERTION_SORT_SIZE Max array size to use insertion sort.
private static final int	MAX_MIXED_INSERTION_SORT_SIZE Max array size to use mixed insertion sort.
private static final int	MAX_RECURSION_DEPTH Max recursive partitioning depth before using heap sort.
private static final int	MAX_RUN_CAPACITY Max capacity of the index array for tracking runs.
private static final int	MAX_SHORT_INDEX Max index of short counter.
private static final int	MIN_BYTE_COUNTING_SORT_SIZE Min size of a byte array to use counting sort.
private static final int	MIN_FIRST_RUN_SIZE Min size of the first run to continue with scanning.
private static final int	MIN_FIRST_RUNS_FACTOR Min factor for the first runs to continue scanning.
private static final int	MIN_PARALLEL_MERGE_PARTS_SIZE Min array size to use parallel merging of parts.
private static final int	MIN_PARALLEL_SORT_SIZE Min array size to perform sorting in parallel.
private static final int	MIN_RUN_COUNT Min number of runs, required by parallel merging.
private static final int	MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE Min size of a short or char array to use counting sort.
private static final int	MIN_TRY_MERGE_SIZE Min array size to try merging of runs.
private static final int	NUM_BYTE_VALUES The number of distinct byte values.
private static final int	NUM_CHAR_VALUES The number of distinct char values.
private static final int	NUM_SHORT_VALUES The number of distinct short values.

Access	Constructor and Description
private	DualPivotQuicksort() Prevents instantiation.

Method Summary

Modifier and Type	Method and Description
private static void	countingSort(byte[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort.
private static void	countingSort(char[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort.
private static void	countingSort(short[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort.
private static int	Returns: the depth of parallel merging getDepth(int the parallelism level parallelism, int the target size size) Calculates the double depth of parallel merging.
private static void	heapSort(int[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using heap sort.
private static void	heapSort(long[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using heap sort.
private static void	heapSort(float[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using heap sort.
private static void	heapSort(double[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using heap sort.
private static void	insertionSort(int[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(long[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(byte[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(char[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(short[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(float[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	insertionSort(double[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using insertion sort.
private static void	mergeParts(DualPivotQuicksort.Merger parallel context merger, int[] the destination where parts are merged dst, int the start index of the destination, inclusive k, int[] the first part a1, int the start index of the first part, inclusive lo1, int the end index of the first part, exclusive hi1, int[] the second part a2, int the start index of the second part, inclusive lo2, int the end index of the second part, exclusive hi2) Merges the sorted parts.
private static void	mergeParts(DualPivotQuicksort.Merger parallel context merger, long[] the destination where parts are merged dst, int the start index of the destination, inclusive k, long[] the first part a1, int the start index of the first part, inclusive lo1, int the end index of the first part, exclusive hi1, long[] the second part a2, int the start index of the second part, inclusive lo2, int the end index of the second part, exclusive hi2) Merges the sorted parts.
private static void	mergeParts(DualPivotQuicksort.Merger parallel context merger, float[] the destination where parts are merged dst, int the start index of the destination, inclusive k, float[] the first part a1, int the start index of the first part, inclusive lo1, int the end index of the first part, exclusive hi1, float[] the second part a2, int the start index of the second part, inclusive lo2, int the end index of the second part, exclusive hi2) Merges the sorted parts.
private static void	mergeParts(DualPivotQuicksort.Merger parallel context merger, double[] the destination where parts are merged dst, int the start index of the destination, inclusive k, double[] the first part a1, int the start index of the first part, inclusive lo1, int the end index of the first part, exclusive hi1, double[] the second part a2, int the start index of the second part, inclusive lo2, int the end index of the second part, exclusive hi2) Merges the sorted parts.
private static int[]	Returns: the destination where runs are merged mergeRuns(int[] the source array a, int[] the temporary buffer used in merging b, int the start index in the source, inclusive offset, int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) aim, boolean indicates whether merging is performed in parallel parallel, int[] the start indexes of the runs, inclusive run, int the start index of the first run, inclusive lo, int the start index of the last run, inclusive hi) Merges the specified runs.
private static long[]	Returns: the destination where runs are merged mergeRuns(long[] the source array a, long[] the temporary buffer used in merging b, int the start index in the source, inclusive offset, int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) aim, boolean indicates whether merging is performed in parallel parallel, int[] the start indexes of the runs, inclusive run, int the start index of the first run, inclusive lo, int the start index of the last run, inclusive hi) Merges the specified runs.
private static float[]	Returns: the destination where runs are merged mergeRuns(float[] the source array a, float[] the temporary buffer used in merging b, int the start index in the source, inclusive offset, int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) aim, boolean indicates whether merging is performed in parallel parallel, int[] the start indexes of the runs, inclusive run, int the start index of the first run, inclusive lo, int the start index of the last run, inclusive hi) Merges the specified runs.
private static double[]	Returns: the destination where runs are merged mergeRuns(double[] the source array a, double[] the temporary buffer used in merging b, int the start index in the source, inclusive offset, int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) aim, boolean indicates whether merging is performed in parallel parallel, int[] the start indexes of the runs, inclusive run, int the start index of the first run, inclusive lo, int the start index of the last run, inclusive hi) Merges the specified runs.
private static void	mixedInsertionSort(int[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using mixed insertion sort.
private static void	mixedInsertionSort(long[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using mixed insertion sort.
private static void	mixedInsertionSort(float[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using mixed insertion sort.
private static void	mixedInsertionSort(double[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using mixed insertion sort.
private static <A> int[]	partition(Class<?> the class of the array to be partitioned elemType, A the array to be partitioned array, long the relative offset, in bytes, from the base address of the array to partition, otherwise if the array is `null`,an absolute address pointing to the first element to partition from. offset, int the index of the first element, inclusive, to be partitioned low, int the index of the last element, exclusive, to be partitioned high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2, DualPivotQuicksort.PartitionOperation<A> the method reference for the fallback implementation po) Partitions the specified range of the array using the two pivots provided.
private static int[]	partitionDualPivot(int[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using the two pivots provided.
private static int[]	partitionDualPivot(long[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using the two pivots provided.
private static int[]	partitionDualPivot(float[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using the two pivots provided.
private static int[]	partitionDualPivot(double[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using the two pivots provided.
private static int[]	partitionSinglePivot(int[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using a single pivot provided.
private static int[]	partitionSinglePivot(long[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using a single pivot provided.
private static int[]	partitionSinglePivot(float[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using a single pivot provided.
private static int[]	partitionSinglePivot(double[] the array to be partitioned a, int the index of the first element, inclusive, for partitioning low, int the index of the last element, exclusive, for partitioning high, int the index of pivot1, the first pivot pivotIndex1, int the index of pivot2, the second pivot pivotIndex2) Partitions the specified range of the array using a single pivot provided.
private static void	pushDown(int[] the given array a, int the start index p, int the given element value, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Pushes specified element down during heap sort.
private static void	pushDown(long[] the given array a, int the start index p, long the given element value, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Pushes specified element down during heap sort.
private static void	pushDown(float[] the given array a, int the start index p, float the given element value, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Pushes specified element down during heap sort.
private static void	pushDown(double[] the given array a, int the start index p, double the given element value, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Pushes specified element down during heap sort.
private static <A> void	sort(Class<?> the class of the elements of the array to be sorted elemType, A the array to be sorted array, long the relative offset, in bytes, from the base address of the array to sort, otherwise if the array is `null`,an absolute address pointing to the first element to sort from. offset, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high, DualPivotQuicksort.SortOperation<A> the method reference for the fallback implementation so) Sorts the specified range of the array into ascending numerical order.
pack-priv static void	sort(int[] the array to be sorted a, int the parallelism level parallelism, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using parallel merge sort and/or Dual-Pivot Quicksort.
pack-priv static void	sort(DualPivotQuicksort.Sorter parallel context sorter, int[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
pack-priv static void	sort(long[] the array to be sorted a, int the parallelism level parallelism, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using parallel merge sort and/or Dual-Pivot Quicksort.
pack-priv static void	sort(DualPivotQuicksort.Sorter parallel context sorter, long[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
pack-priv static void	sort(byte[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort or insertion sort.
pack-priv static void	sort(char[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort or Dual-Pivot Quicksort.
pack-priv static void	sort(char[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
pack-priv static void	sort(short[] the array to be sorted a, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using counting sort or Dual-Pivot Quicksort.
pack-priv static void	sort(short[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
pack-priv static void	sort(float[] the array to be sorted a, int the parallelism level parallelism, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using parallel merge sort and/or Dual-Pivot Quicksort.
pack-priv static void	sort(DualPivotQuicksort.Sorter parallel context sorter, float[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
pack-priv static void	sort(double[] the array to be sorted a, int the parallelism level parallelism, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified range of the array using parallel merge sort and/or Dual-Pivot Quicksort.
pack-priv static void	sort(DualPivotQuicksort.Sorter parallel context sorter, double[] the array to be sorted a, int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part bits, int the index of the first element, inclusive, to be sorted low, int the index of the last element, exclusive, to be sorted high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.
private static boolean	Returns: true if finally sorted, false otherwise tryMergeRuns(DualPivotQuicksort.Sorter parallel context sorter, int[] the array to be sorted a, int the index of the first element to be sorted low, int the array size size) Tries to sort the specified range of the array.
private static boolean	Returns: true if finally sorted, false otherwise tryMergeRuns(DualPivotQuicksort.Sorter parallel context sorter, long[] the array to be sorted a, int the index of the first element to be sorted low, int the array size size) Tries to sort the specified range of the array.
private static boolean	Returns: true if finally sorted, false otherwise tryMergeRuns(DualPivotQuicksort.Sorter parallel context sorter, float[] the array to be sorted a, int the index of the first element to be sorted low, int the array size size) Tries to sort the specified range of the array.
private static boolean	Returns: true if finally sorted, false otherwise tryMergeRuns(DualPivotQuicksort.Sorter parallel context sorter, double[] the array to be sorted a, int the index of the first element to be sorted low, int the array size size) Tries to sort the specified range of the array.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

pack-priv final Class DualPivotQuicksort

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary