Class IntroSorter

java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.IntroSorter

public abstract class IntroSorter extends Sorter
Sorter implementation based on a variant of the quicksort algorithm called introsort: when the recursion level exceeds the log of the length of the array to sort, it falls back to heapsort. This prevents quicksort from running into its worst-case quadratic runtime. Small arrays are sorted with insertion sort.
  • Constructor Details

    • IntroSorter

      public IntroSorter()
      Create a new IntroSorter.
  • Method Details

    • sort

      public final 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
    • setPivot

      protected abstract 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 abstract int comparePivot(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).