Package com.carrotsearch.hppc.sorting
Class IndirectSort
java.lang.Object
com.carrotsearch.hppc.sorting.IndirectSort
Sorting routines that return an array of sorted indices implied by a given
comparator rather than move elements of whatever the comparator is using for
comparisons.
A practical use case for this class is when the index of an array is
meaningful and one wants to acquire the order of values in that array. None
of the methods in Java Collections would provide such functionality directly
and creating a collection of boxed Integer
objects for indices seems
to be too costly.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) static int
Minimum window length to apply insertion sort in merge sort. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static int[]
createOrderArray
(int start, int length) Creates the initial order array.private static void
insertionSort
(int off, int len, int[] order, IndirectComparator intComparator) Internal insertion sort forint
s.static int[]
mergesort
(int start, int length, IndirectComparator comparator) Returns the order of elements between indicesstart
andlength
, as indicated by the givencomparator
.static <T> int[]
mergesort
(T[] input, int start, int length, Comparator<? super T> comparator) Returns the order of elements between indicesstart
andlength
, as indicated by the givencomparator
.private static void
topDownMergeSort
(int[] src, int[] dst, int fromIndex, int toIndex, IndirectComparator comp) Perform a recursive, descending merge sort.
-
Field Details
-
MIN_LENGTH_FOR_INSERTION_SORT
static int MIN_LENGTH_FOR_INSERTION_SORTMinimum window length to apply insertion sort in merge sort.
-
-
Constructor Details
-
IndirectSort
private IndirectSort()No instantiation.
-
-
Method Details
-
mergesort
Returns the order of elements between indicesstart
andlength
, as indicated by the givencomparator
.This routine uses merge sort. It is guaranteed to be stable.
-
mergesort
public static <T> int[] mergesort(T[] input, int start, int length, Comparator<? super T> comparator) Returns the order of elements between indicesstart
andlength
, as indicated by the givencomparator
. This method is equivalent to callingmergesort(int, int, IndirectComparator)
withIndirectComparator.DelegatingComparator
.This routine uses merge sort. It is guaranteed to be stable.
-
topDownMergeSort
private static void topDownMergeSort(int[] src, int[] dst, int fromIndex, int toIndex, IndirectComparator comp) Perform a recursive, descending merge sort.- Parameters:
fromIndex
- inclusivetoIndex
- exclusive
-
insertionSort
Internal insertion sort forint
s. -
createOrderArray
private static int[] createOrderArray(int start, int length) Creates the initial order array.
-