public final class IndirectSort
extends java.lang.Object
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.
| Modifier and Type | Field and Description |
|---|---|
(package private) static int |
MIN_LENGTH_FOR_INSERTION_SORT
Minimum window length to apply insertion sort in merge sort.
|
| Modifier | Constructor and Description |
|---|---|
private |
IndirectSort()
No instantiation.
|
| Modifier and Type | Method and Description |
|---|---|
private 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 for
ints. |
static int[] |
mergesort(int start,
int length,
IndirectComparator comparator)
Returns the order of elements between indices
start and
length, as indicated by the given comparator. |
static <T> int[] |
mergesort(T[] input,
int start,
int length,
java.util.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 fromIndex,
int toIndex,
IndirectComparator comp)
Perform a recursive, descending merge sort.
|
static int MIN_LENGTH_FOR_INSERTION_SORT
public static int[] mergesort(int start,
int length,
IndirectComparator comparator)
start and
length, as indicated by the given comparator.
This routine uses merge sort. It is guaranteed to be stable.
public static <T> int[] mergesort(T[] input,
int start,
int length,
java.util.Comparator<? super T> comparator)
start and
length, as indicated by the given comparator.
This method is equivalent to calling
mergesort(int, int, IndirectComparator) with
IndirectComparator.DelegatingComparator.
This routine uses merge sort. It is guaranteed to be stable.
private static void topDownMergeSort(int[] src,
int[] dst,
int fromIndex,
int toIndex,
IndirectComparator comp)
fromIndex - inclusivetoIndex - exclusiveprivate static void insertionSort(int off,
int len,
int[] order,
IndirectComparator intComparator)
ints.private static int[] createOrderArray(int start,
int length)