Package com.carrotsearch.hppc.sorting

Class IndirectSort

  • public final class IndirectSort
extends java.lang.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 MIN_LENGTH_FOR_INSERTION_SORT
      Minimum window length to apply insertion sort in merge sort.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private IndirectSort()
      No instantiation.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      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, 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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • MIN_LENGTH_FOR_INSERTION_SORT

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

    • Constructor Detail

      • IndirectSort

        private IndirectSort()
        No instantiation.

    • Method Detail

      • 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,
                                  java.util.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.