Class IndirectSort

java.lang.Object
com.carrotsearch.hppc.sorting.IndirectSort

public final class IndirectSort extends Object
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

    Fields
    Modifier and Type
    Field
    Description
    (package private) static int
    Minimum window length to apply insertion sort in merge sort.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    No instantiation.
  • Method Summary

    Modifier and Type
    Method
    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, 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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • MIN_LENGTH_FOR_INSERTION_SORT

      static int MIN_LENGTH_FOR_INSERTION_SORT
      Minimum window length to apply insertion sort in merge sort.
  • Constructor Details

    • IndirectSort

      private IndirectSort()
      No instantiation.
  • Method Details

    • mergesort

      public 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.

      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 indices 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.

    • topDownMergeSort

      private static void topDownMergeSort(int[] src, int[] dst, int fromIndex, int toIndex, IndirectComparator comp)
      Perform a recursive, descending merge sort.
      Parameters:
      fromIndex - inclusive
      toIndex - exclusive
    • insertionSort

      private static void insertionSort(int off, int len, int[] order, IndirectComparator intComparator)
      Internal insertion sort for ints.
    • createOrderArray

      private static int[] createOrderArray(int start, int length)
      Creates the initial order array.