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
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. Selects the pivot using Tukey's ninther
median-of-medians, and partitions using Bentley-McIlroy 3-way partitioning. Small ranges are
sorted with insertion sort.
This algorithm is NOT stable. It's fast on most data shapes, especially with low
cardinality. If the data to sort is known to be strictly ascending or descending, prefer TimSorter
.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) static final int
Below this size threshold, the partition selection is simplified to a single median.Fields inherited from class org.apache.lucene.util.Sorter
BINARY_SORT_THRESHOLD, INSERTION_SORT_THRESHOLD
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected 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)
.private int
median
(int i, int j, int k) Returns the index of the median element among three elements at provided indices.protected abstract void
setPivot
(int i) Save the value at sloti
so that it can later be used as a pivot, seeSorter.comparePivot(int)
.final void
sort
(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).(package private) void
sort
(int from, int to, int maxDepth) Sorts between from (inclusive) and to (exclusive) with intro sort.Methods inherited from class org.apache.lucene.util.Sorter
binarySort, binarySort, checkRange, doRotate, heapChild, heapify, heapParent, heapSort, insertionSort, lower, lower2, mergeInPlace, reverse, rotate, siftDown, swap, upper, upper2
-
Field Details
-
SINGLE_MEDIAN_THRESHOLD
static final int SINGLE_MEDIAN_THRESHOLDBelow this size threshold, the partition selection is simplified to a single median.- See Also:
-
-
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). -
sort
void sort(int from, int to, int maxDepth) Sorts between from (inclusive) and to (exclusive) with intro sort.Sorts small ranges with insertion sort. Fallbacks to heap sort to avoid quadratic worst case. Selects the pivot with medians and partitions with the Bentley-McIlroy fast 3-ways algorithm (Engineering a Sort Function, Bentley-McIlroy).
-
median
private int median(int i, int j, int k) Returns the index of the median element among three elements at provided indices. -
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
-
compare
protected int compare(int i, int j) Description copied from class:Sorter
Compare entries found in slotsi
andj
. The contract for the returned value is the same asComparator.compare(Object, Object)
.
-