Package org.apache.lucene.util
Class IntroSorter
- java.lang.Object
-
- org.apache.lucene.util.Sorter
-
- org.apache.lucene.util.IntroSorter
-
- Direct Known Subclasses:
ArrayIntroSorter
,CollectionUtil.ListIntroSorter
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.
-
-
Field Summary
-
Fields inherited from class org.apache.lucene.util.Sorter
BINARY_SORT_THRESHOLD
-
-
Constructor Summary
Constructors Constructor Description IntroSorter()
Create a newIntroSorter
.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected int
compare(int i, int j)
Compare entries found in slotsi
andj
.protected abstract int
comparePivot(int j)
Compare the pivot with the slot atj
, similarly tocompare(i, j)
.(package private) void
quicksort(int from, int to, int maxDepth)
protected abstract void
setPivot(int i)
Save the value at sloti
so that it can later be used as a pivot, seeSorter.comparePivot(int)
.void
sort(int from, int to)
Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).-
Methods inherited from class org.apache.lucene.util.Sorter
binarySort, binarySort, checkRange, doRotate, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, siftDown, swap, upper, upper2
-
-
-
-
Constructor Detail
-
IntroSorter
public IntroSorter()
Create a newIntroSorter
.
-
-
Method Detail
-
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).
-
quicksort
void quicksort(int from, int to, int maxDepth)
-
setPivot
protected abstract void setPivot(int i)
Description copied from class:Sorter
Save the value at sloti
so that it can later be used as a pivot, seeSorter.comparePivot(int)
.
-
comparePivot
protected abstract int comparePivot(int j)
Description copied from class:Sorter
Compare the pivot with the slot atj
, similarly tocompare(i, j)
.- Overrides:
comparePivot
in classSorter
-
-