OpenJDK 27 · sun.java2d.marlin.DualPivotQuicksort20191112Ext

Modifier and Type	Field and Description
private static final int	DELTA Threshold of mixed insertion sort is incremented by this value.
private static final boolean	FAST_ISORT
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.
pack-priv static final int	MAX_RUN_CAPACITY Max capacity of the index array for tracking runs.
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_TRY_MERGE_SIZE Min array size to try merging of runs.

Access	Constructor and Description
private	DualPivotQuicksort20191112Ext() Prevents instantiation.

Method Summary

Modifier and Type	Method and Description
private static void	heapSort(int[] the array to be sorted a, int[] the secondary array to be ordered b, 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.
pack-priv static void	insertionSort(int[] the array to be sorted a, int[] the secondary array to be ordered b, 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(int[] the destination where parts are merged (a) dstA, int[] the destination where parts are merged (b) dstB, int the start index of the destination, inclusive k, int[] the first part (a) a1, int[] the first part (b) b1, int the start index of the first part, inclusive lo1, int the end index of the first part, exclusive hi1, int[] the second part (a) a2, int[] the second part (b) b2, 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 for the array to be sorted (a) srcA, int[] the temporary buffer used in merging (a) dstA, int[] the source array for the secondary array to be ordered (b) srcB, int[] the temporary buffer used in merging (b) dstB, int the start index in the source, inclusive offset, int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) aim, 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 secondary array to be ordered b, int the index of the first element, inclusive, to be sorted low, int the index of the last element for simple insertion sort end, 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	pushDown(int[] the array to be sorted a, int[] the secondary array to be ordered b, int the start index p, int the given element in a valueA, int the given element in b valueB, 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.
pack-priv static void	sort(DPQSSorterContext sorter context sorter, int[] the array to be sorted a, int[] auxiliary storage for the array to be sorted auxA, int[] the secondary array to be ordered b, int[] auxiliary storage for the permutation array to be handled auxB, 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.
private static void	sort(DPQSSorterContext sorter context sorter, int[] the array to be sorted a, int[] the secondary array to be ordered b, 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(DPQSSorterContext sorter context sorter, int[] the array to be sorted a, int[] the secondary array to be ordered b, 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

DELTA	back to summary
private static final int DELTA Threshold of mixed insertion sort is incremented by this value.

FAST_ISORT	back to summary
private static final boolean FAST_ISORT

MAX_INSERTION_SORT_SIZE	back to summary
private static final int MAX_INSERTION_SORT_SIZE Max array size to use insertion sort.

MAX_MIXED_INSERTION_SORT_SIZE	back to summary
private static final int MAX_MIXED_INSERTION_SORT_SIZE Max array size to use mixed insertion sort.

MAX_RECURSION_DEPTH	back to summary
private static final int MAX_RECURSION_DEPTH Max recursive partitioning depth before using heap sort.

MAX_RUN_CAPACITY	back to summary
pack-priv static final int MAX_RUN_CAPACITY Max capacity of the index array for tracking runs.

MIN_FIRST_RUN_SIZE	back to summary
private static final int MIN_FIRST_RUN_SIZE Min size of the first run to continue with scanning.

MIN_FIRST_RUNS_FACTOR	back to summary
private static final int MIN_FIRST_RUNS_FACTOR Min factor for the first runs to continue scanning.

MIN_TRY_MERGE_SIZE	back to summary
private static final int MIN_TRY_MERGE_SIZE Min array size to try merging of runs.

DualPivotQuicksort20191112Ext	back to summary
private DualPivotQuicksort20191112Ext() Prevents instantiation.

Method Detail

heapSort	back to summary
private static void heapSort(int[] a, int[] b, int low, int high) Sorts the specified range of the array using heap sort. Parameters a:int[] the array to be sorted b:int[] the secondary array to be ordered low:int the index of the first element, inclusive, to be sorted high:int the index of the last element, exclusive, to be sorted

heapSort

back to summary

private static void heapSort(int[] a, int[] b, int low, int high)

Sorts the specified range of the array using heap sort.

Parameters

a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
low:int: the index of the first element, inclusive, to be sorted
high:int: the index of the last element, exclusive, to be sorted

insertionSort	back to summary
pack-priv static void insertionSort(int[] a, int[] b, int low, int high) Sorts the specified range of the array using insertion sort. Parameters a:int[] the array to be sorted b:int[] the secondary array to be ordered low:int the index of the first element, inclusive, to be sorted high:int the index of the last element, exclusive, to be sorted

insertionSort

back to summary

pack-priv static void insertionSort(int[] a, int[] b, int low, int high)

Sorts the specified range of the array using insertion sort.

Parameters

a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
low:int: the index of the first element, inclusive, to be sorted
high:int: the index of the last element, exclusive, to be sorted

mergeParts	back to summary
private static void mergeParts(int[] dstA, int[] dstB, int k, int[] a1, int[] b1, int lo1, int hi1, int[] a2, int[] b2, int lo2, int hi2) Merges the sorted parts. Parameters dstA:int[] the destination where parts are merged (a) dstB:int[] the destination where parts are merged (b) k:int the start index of the destination, inclusive a1:int[] the first part (a) b1:int[] the first part (b) lo1:int the start index of the first part, inclusive hi1:int the end index of the first part, exclusive a2:int[] the second part (a) b2:int[] the second part (b) lo2:int the start index of the second part, inclusive hi2:int the end index of the second part, exclusive

mergeParts

back to summary

private static void mergeParts(int[] dstA, int[] dstB, int k, int[] a1, int[] b1, int lo1, int hi1, int[] a2, int[] b2, int lo2, int hi2)

Merges the sorted parts.

Parameters

dstA:int[]: the destination where parts are merged (a)
dstB:int[]: the destination where parts are merged (b)
k:int: the start index of the destination, inclusive
a1:int[]: the first part (a)
b1:int[]: the first part (b)
lo1:int: the start index of the first part, inclusive
hi1:int: the end index of the first part, exclusive
a2:int[]: the second part (a)
b2:int[]: the second part (b)
lo2:int: the start index of the second part, inclusive
hi2:int: the end index of the second part, exclusive

mergeRuns	back to summary
private static int[] mergeRuns(int[] srcA, int[] dstA, int[] srcB, int[] dstB, int offset, int aim, int[] run, int lo, int hi) Merges the specified runs. Parameters srcA:int[] the source array for the array to be sorted (a) dstA:int[] the temporary buffer used in merging (a) srcB:int[] the source array for the secondary array to be ordered (b) dstB:int[] the temporary buffer used in merging (b) offset:int the start index in the source, inclusive aim:int specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0) run:int[] the start indexes of the runs, inclusive lo:int the start index of the first run, inclusive hi:int the start index of the last run, inclusive Returns:int[] the destination where runs are merged

mergeRuns

back to summary

private static int[] mergeRuns(int[] srcA, int[] dstA, int[] srcB, int[] dstB, int offset, int aim, int[] run, int lo, int hi)

Merges the specified runs.

Parameters

srcA:int[]: the source array for the array to be sorted (a)
dstA:int[]: the temporary buffer used in merging (a)
srcB:int[]: the source array for the secondary array to be ordered (b)
dstB:int[]: the temporary buffer used in merging (b)
offset:int: the start index in the source, inclusive
aim:int: specifies merging: to source ( > 0), buffer ( < 0) or any ( == 0)
run:int[]: the start indexes of the runs, inclusive
lo:int: the start index of the first run, inclusive
hi:int: the start index of the last run, inclusive

Returns:int[]

the destination where runs are merged

mixedInsertionSort	back to summary
private static void mixedInsertionSort(int[] a, int[] b, int low, int end, int high) 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. Parameters a:int[] the array to be sorted b:int[] the secondary array to be ordered low:int the index of the first element, inclusive, to be sorted end:int the index of the last element for simple insertion sort high:int the index of the last element, exclusive, to be sorted

mixedInsertionSort

back to summary

private static void mixedInsertionSort(int[] a, int[] b, int low, int end, int high)

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.

Parameters

a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
low:int: the index of the first element, inclusive, to be sorted
end:int: the index of the last element for simple insertion sort
high:int: the index of the last element, exclusive, to be sorted

pushDown	back to summary
private static void pushDown(int[] a, int[] b, int p, int valueA, int valueB, int low, int high) Pushes specified element down during heap sort. Parameters a:int[] the array to be sorted b:int[] the secondary array to be ordered p:int the start index valueA:int the given element in a valueB:int the given element in b low:int the index of the first element, inclusive, to be sorted high:int the index of the last element, exclusive, to be sorted

pushDown

back to summary

private static void pushDown(int[] a, int[] b, int p, int valueA, int valueB, int low, int high)

Pushes specified element down during heap sort.

Parameters

a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
p:int: the start index
valueA:int: the given element in a
valueB:int: the given element in b
low:int: the index of the first element, inclusive, to be sorted
high:int: the index of the last element, exclusive, to be sorted

sort	back to summary
pack-priv static void sort(DPQSSorterContext sorter, int[] a, int[] auxA, int[] b, int[] auxB, int low, int high) Sorts the specified range of the array. Parameters sorter:DPQSSorterContext sorter context a:int[] the array to be sorted auxA:int[] auxiliary storage for the array to be sorted b:int[] the secondary array to be ordered auxB:int[] auxiliary storage for the permutation array to be handled low:int the index of the first element, inclusive, to be sorted high:int the index of the last element, exclusive, to be sorted

sort

back to summary

pack-priv static void sort(DPQSSorterContext sorter, int[] a, int[] auxA, int[] b, int[] auxB, int low, int high)

Sorts the specified range of the array.

Parameters

sorter:DPQSSorterContext: sorter context
a:int[]: the array to be sorted
auxA:int[]: auxiliary storage for the array to be sorted
b:int[]: the secondary array to be ordered
auxB:int[]: auxiliary storage for the permutation array to be handled
low:int: the index of the first element, inclusive, to be sorted
high:int: the index of the last element, exclusive, to be sorted

sort	back to summary
private static void sort(DPQSSorterContext sorter, int[] a, int[] b, int bits, int low, int high) Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions. Parameters sorter:DPQSSorterContext sorter context a:int[] the array to be sorted b:int[] the secondary array to be ordered bits:int the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part low:int the index of the first element, inclusive, to be sorted high:int the index of the last element, exclusive, to be sorted

sort

back to summary

private static void sort(DPQSSorterContext sorter, int[] a, int[] b, int bits, int low, int high)

Sorts the specified array using the Dual-Pivot Quicksort and/or other sorts in special-cases, possibly with parallel partitions.

Parameters

sorter:DPQSSorterContext: sorter context
a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
bits:int: the combination of recursion depth and bit flag, where the right bit "0" indicates that array is the leftmost part
low:int: the index of the first element, inclusive, to be sorted
high:int: the index of the last element, exclusive, to be sorted

tryMergeRuns	back to summary
private static boolean tryMergeRuns(DPQSSorterContext sorter, int[] a, int[] b, int low, int size) Tries to sort the specified range of the array. Parameters sorter:DPQSSorterContext sorter context a:int[] the array to be sorted b:int[] the secondary array to be ordered low:int the index of the first element to be sorted size:int the array size Returns:boolean true if finally sorted, false otherwise

tryMergeRuns

back to summary

private static boolean tryMergeRuns(DPQSSorterContext sorter, int[] a, int[] b, int low, int size)

Tries to sort the specified range of the array.

Parameters

sorter:DPQSSorterContext: sorter context
a:int[]: the array to be sorted
b:int[]: the secondary array to be ordered
low:int: the index of the first element to be sorted
size:int: the array size

Returns:boolean

true if finally sorted, false otherwise

public final Class DualPivotQuicksort20191112Ext

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail