Class TimSorter

  • Direct Known Subclasses:
    ArrayTimSorter, CollectionUtil.ListTimSorter, FreqProxTermsWriter.SortingPostingsEnum.DocOffsetSorter, Sorter.DocValueSorter

    public abstract class TimSorter
    extends Sorter
    Sorter implementation based on the TimSort algorithm. It sorts small arrays with a binary sort.

    This algorithm is stable. It's especially good at sorting partially-sorted arrays.

    NOTE:There are a few differences with the original implementation:

    • The extra amount of memory to perform merges is configurable. This allows small merges to be very fast while large merges will be performed in-place (slightly slower). You can make sure that the fast merge routine will always be used by having maxTempSlots equal to half of the length of the slice of data to sort.
    • Only the fast merge routine can gallop (the one that doesn't run in-place) and it only gallops on the longest slice.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected TimSorter​(int maxTempSlots)
      Create a new TimSorter.
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected abstract int compareSaved​(int i, int j)
      Compare element i from the temporary storage with element j from the slice to sort, similarly to Sorter.compare(int, int).
      protected abstract void copy​(int src, int dest)
      Copy data from slot src to slot dest.
      (package private) void doRotate​(int lo, int mid, int hi)  
      (package private) void ensureInvariants()  
      (package private) void exhaustStack()  
      (package private) int lowerSaved​(int from, int to, int val)  
      (package private) int lowerSaved3​(int from, int to, int val)  
      (package private) void merge​(int lo, int mid, int hi)  
      (package private) void mergeAt​(int n)  
      (package private) void mergeHi​(int lo, int mid, int hi)  
      (package private) void mergeLo​(int lo, int mid, int hi)  
      (package private) static int minRun​(int length)
      Minimum run length for an array of length length.
      (package private) int nextRun()
      Compute the length of the next run, make the run sorted and return its length.
      (package private) void pushRunLen​(int len)  
      (package private) void reset​(int from, int to)  
      protected abstract void restore​(int i, int j)
      Restore element j from the temporary storage into slot i.
      (package private) int runBase​(int i)  
      (package private) int runEnd​(int i)  
      (package private) int runLen​(int i)  
      protected abstract void save​(int i, int len)
      Save all elements between slots i and i+len into the temporary storage.
      (package private) void setRunEnd​(int i, int runEnd)  
      void sort​(int from, int to)
      Sort the slice which starts at from (inclusive) and ends at to (exclusive).
      (package private) int upperSaved​(int from, int to, int val)  
      (package private) int upperSaved3​(int from, int to, int val)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Method Detail

      • minRun

        static int minRun​(int length)
        Minimum run length for an array of length length.
      • runLen

        int runLen​(int i)
      • runBase

        int runBase​(int i)
      • runEnd

        int runEnd​(int i)
      • setRunEnd

        void setRunEnd​(int i,
                       int runEnd)
      • pushRunLen

        void pushRunLen​(int len)
      • nextRun

        int nextRun()
        Compute the length of the next run, make the run sorted and return its length.
      • ensureInvariants

        void ensureInvariants()
      • exhaustStack

        void exhaustStack()
      • reset

        void reset​(int from,
                   int to)
      • mergeAt

        void mergeAt​(int n)
      • merge

        void merge​(int lo,
                   int mid,
                   int hi)
      • sort

        public void sort​(int from,
                         int to)
        Description copied from class: Sorter
        Sort the slice which starts at from (inclusive) and ends at to (exclusive).
        Specified by:
        sort in class Sorter
      • doRotate

        void doRotate​(int lo,
                      int mid,
                      int hi)
        Overrides:
        doRotate in class Sorter
      • mergeLo

        void mergeLo​(int lo,
                     int mid,
                     int hi)
      • mergeHi

        void mergeHi​(int lo,
                     int mid,
                     int hi)
      • lowerSaved

        int lowerSaved​(int from,
                       int to,
                       int val)
      • upperSaved

        int upperSaved​(int from,
                       int to,
                       int val)
      • lowerSaved3

        int lowerSaved3​(int from,
                        int to,
                        int val)
      • upperSaved3

        int upperSaved3​(int from,
                        int to,
                        int val)
      • copy

        protected abstract void copy​(int src,
                                     int dest)
        Copy data from slot src to slot dest.
      • save

        protected abstract void save​(int i,
                                     int len)
        Save all elements between slots i and i+len into the temporary storage.
      • restore

        protected abstract void restore​(int i,
                                        int j)
        Restore element j from the temporary storage into slot i.
      • compareSaved

        protected abstract int compareSaved​(int i,
                                            int j)
        Compare element i from the temporary storage with element j from the slice to sort, similarly to Sorter.compare(int, int).