Package org.apache.lucene.util
Class IntroSorter
java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.IntroSorter
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 Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected abstract int
comparePivot
(int j) Compare the pivot with the slot atj
, similarly tocompare(i, j)
.protected abstract void
setPivot
(int i) Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.final void
sort
(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).
-
Constructor Details
-
IntroSorter
public IntroSorter()Create a newIntroSorter
.
-
-
Method Details
-
sort
public final void sort(int from, int to) Description copied from class:Sorter
Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive). -
setPivot
protected abstract void setPivot(int i) Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
. -
comparePivot
protected abstract int comparePivot(int j) Compare the pivot with the slot atj
, similarly tocompare(i, j)
.
-