Package org.apache.lucene.util

Class TimSorter

java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.TimSorter
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.
NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    TimSorter(int maxTempSlots)
    Create a new TimSorter.

  • Method Summary

    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.
    protected abstract void
    restore(int i, int j)
    Restore element j from the temporary storage into slot i.
    protected abstract void
    save(int i, int len)
    Save all elements between slots i and i+len into the temporary storage.
    void
    sort(int from, int to)
    Sort the slice which starts at from (inclusive) and ends at to (exclusive).

    Methods inherited from class org.apache.lucene.util.Sorter

    compare, comparePivot, setPivot, swap

    Methods inherited from class java.lang.Object

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

  • Constructor Details

  • Method Details

    • 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

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