Class TimSorter

java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.TimSorter
Direct Known Subclasses:
ArrayTimSorter, CollectionUtil.ListTimSorter, FreqProxTermsWriter.SortingDocsEnum.DocFreqSorter, 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.
  • Field Details

  • Constructor Details

  • Method Details

    • 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).