Top Description Fields Constructors Methods
com.carrotsearch.hppc.sorting

public final Class IndirectSort

extends Object
Class Inheritance
Imports
java.util.Comparator, java.util.function.IntBinaryOperator
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

Modifier and TypeField and Description
pack-priv static int
MIN_LENGTH_FOR_INSERTION_SORT

Minimum window length to apply insertion sort in merge sort.

Constructor Summary

AccessConstructor and Description
private
IndirectSort()

No instantiation.

Method Summary

Modifier and TypeMethod and Description
private static int[]
createOrderArray(final int start, final int length)

Creates the initial order array.

private static void
insertionSort(final int off, final int len, int[] order, IntBinaryOperator intComparator)

Internal insertion sort for ints.

public static int[]
mergesort(int start, int length, IntBinaryOperator comparator)

Returns the order of elements between indices start and length, as indicated by the given comparator.

public static int[]
mergesort(int[] orderArray, IntBinaryOperator comparator)

Returns a sorted copy of the order array provided, using the given comparator.

public static <T> int[]
mergesort(T[] input, int start, int length, Comparator<? super T> comparator)

Returns the order of elements between indices start and length, as indicated by the given comparator.

private static void
topDownMergeSort(int[] src, int[] dst, int
inclusive
fromIndex, int
exclusive
toIndex, IntBinaryOperator comp)

Perform a recursive, descending merge sort.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

MIN_LENGTH_FOR_INSERTION_SORTback to summary
pack-priv static int MIN_LENGTH_FOR_INSERTION_SORT

Minimum window length to apply insertion sort in merge sort.

Constructor Detail

IndirectSortback to summary
private IndirectSort()

No instantiation.

Method Detail

createOrderArrayback to summary
private static int[] createOrderArray(final int start, final int length)

Creates the initial order array.

insertionSortback to summary
private static void insertionSort(final int off, final int len, int[] order, IntBinaryOperator intComparator)

Internal insertion sort for ints.

mergesortback to summary
public static int[] mergesort(int start, int length, IntBinaryOperator comparator)

Returns the order of elements between indices start and length, as indicated by the given comparator.

This routine uses merge sort. It is guaranteed to be stable. It creates a new indices array, and clones it while sorting.

mergesortback to summary
public static int[] mergesort(int[] orderArray, IntBinaryOperator comparator)

Returns a sorted copy of the order array provided, using the given comparator.

This routine uses merge sort. It is guaranteed to be stable. The provided indicesArray is cloned while sorting and the clone is returned.

mergesortback to summary
public static <T> int[] mergesort(T[] input, int start, int length, Comparator<? super T> comparator)

Returns the order of elements between indices start and length, as indicated by the given comparator.

This routine uses merge sort. It is guaranteed to be stable. It creates a new indices array, and clones it while sorting.

topDownMergeSortback to summary
private static void topDownMergeSort(int[] src, int[] dst, int fromIndex, int toIndex, IntBinaryOperator comp)

Perform a recursive, descending merge sort.

Parameters
fromIndex:int

inclusive

toIndex:int

exclusive