Module org.apache.lucene.core
Package org.apache.lucene.util

Class Sorter

java.lang.Object
org.apache.lucene.util.Sorter
Direct Known Subclasses:
InPlaceMergeSorter, IntroSorter, MSBRadixSorter, StableMSBRadixSorter.MergeSorter, StringSorter, TimSorter
public abstract class Sorter extends Object
Base class for sorting algorithms implementations.

There are a number of subclasses to choose from that vary in performance and stability. We suggest that you pick the first from this ranked list that meets your requirements:

  1. MSBRadixSorter for strings (array of bytes/chars). Not a stable sort.
  2. StableMSBRadixSorter for strings (array of bytes/chars). Stable sort.
  3. IntroSorter. Not a stable sort.
  4. InPlaceMergeSorter. When the data to sort is typically small. Stable sort.
  5. TimSorter. Stable sort.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) static final int
    BINARY_SORT_THRESHOLD
     
    (package private) static final int
    INSERTION_SORT_THRESHOLD
    Below this size threshold, the sub-range is sorted using Insertion sort.
    private int
    pivotIndex
     

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Sorter()
    Sole constructor, used for inheritance.

  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) void
    binarySort(int from, int to)
    A binary sort implementation.
    (package private) void
    binarySort(int from, int to, int i)
     
    (package private) void
    checkRange(int from, int to)
     
    protected abstract int
    compare(int i, int j)
    Compare entries found in slots i and j.
    protected int
    comparePivot(int j)
    Compare the pivot with the slot at j, similarly to compare(i, j).
    (package private) void
    doRotate(int lo, int mid, int hi)
     
    (package private) static int
    heapChild(int from, int i)
     
    (package private) void
    heapify(int from, int to)
     
    (package private) static int
    heapParent(int from, int i)
     
    (package private) void
    heapSort(int from, int to)
    Use heap sort to sort items between from inclusive and to exclusive.
    (package private) void
    insertionSort(int from, int to)
    Sorts between from (inclusive) and to (exclusive) with insertion sort.
    (package private) int
    lower(int from, int to, int val)
     
    (package private) int
    lower2(int from, int to, int val)
     
    (package private) void
    mergeInPlace(int from, int mid, int to)
     
    (package private) final void
    reverse(int from, int to)
     
    (package private) final void
    rotate(int lo, int mid, int hi)
     
    protected void
    setPivot(int i)
    Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
    (package private) void
    siftDown(int i, int from, int to)
     
    abstract void
    sort(int from, int to)
    Sort the slice which starts at from (inclusive) and ends at to (exclusive).
    protected abstract void
    swap(int i, int j)
    Swap values at slots i and j.
    (package private) int
    upper(int from, int to, int val)
     
    (package private) int
    upper2(int from, int to, int val)
     

    Methods inherited from class java.lang.Object

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

  • Field Details

    • BINARY_SORT_THRESHOLD

      static final int BINARY_SORT_THRESHOLD
      See Also:

    • INSERTION_SORT_THRESHOLD

      static final int INSERTION_SORT_THRESHOLD
      Below this size threshold, the sub-range is sorted using Insertion sort.
      See Also:

    • pivotIndex

      private int pivotIndex

  • Constructor Details

    • Sorter

      protected Sorter()
      Sole constructor, used for inheritance.

  • Method Details

    • compare

      protected abstract int compare(int i, int j)
      Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).

    • swap

      protected abstract void swap(int i, int j)
      Swap values at slots i and j.

    • setPivot

      protected void setPivot(int i)
      Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).

    • comparePivot

      protected int comparePivot(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).

    • sort

      public abstract void sort(int from, int to)
      Sort the slice which starts at from (inclusive) and ends at to (exclusive).

    • checkRange

      void checkRange(int from, int to)

    • mergeInPlace

      void mergeInPlace(int from, int mid, int to)

    • lower

      int lower(int from, int to, int val)

    • upper

      int upper(int from, int to, int val)

    • lower2

      int lower2(int from, int to, int val)

    • upper2

      int upper2(int from, int to, int val)

    • reverse

      final void reverse(int from, int to)

    • rotate

      final void rotate(int lo, int mid, int hi)

    • doRotate

      void doRotate(int lo, int mid, int hi)

    • binarySort

      void binarySort(int from, int to)
      A binary sort implementation. This performs O(n*log(n)) comparisons and O(n^2) swaps. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort has become less than 20. This algorithm is stable.

    • binarySort

      void binarySort(int from, int to, int i)

    • insertionSort

      void insertionSort(int from, int to)
      Sorts between from (inclusive) and to (exclusive) with insertion sort. Runs in O(n^2). It is typically used by more sophisticated implementations as a fall-back when the number of items to sort becomes less than 16. This algorithm is stable.

    • heapSort

      void heapSort(int from, int to)
      Use heap sort to sort items between from inclusive and to exclusive. This runs in O(n*log(n)) and is used as a fall-back by IntroSorter. This algorithm is NOT stable.

    • heapify

      void heapify(int from, int to)

    • siftDown

      void siftDown(int i, int from, int to)

    • heapParent

      static int heapParent(int from, int i)

    • heapChild

      static int heapChild(int from, int i)