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. 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

Fields

Modifier and Type	Field	Description
(package private) static int	SINGLE_MEDIAN_THRESHOLD	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

Constructor	Description
IntroSorter()	Create a new IntroSorter.

Method Summary

Modifier and Type	Method	Description
protected int	compare(int i, int j)	Compare entries found in slots i and j.
protected abstract int	comparePivot(int j)	Compare the pivot with the slot at j, similarly to compare(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 slot i so that it can later be used as a pivot, see Sorter.comparePivot(int).
void	sort(int from, int to)	Sort the slice which starts at from (inclusive) and ends at to (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

Methods inherited from class java.lang.Object

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

Field Detail

SINGLE_MEDIAN_THRESHOLD

static final int SINGLE_MEDIAN_THRESHOLD

Below this size threshold, the partition selection is simplified to a single median.

See Also:

Constant Field Values

Constructor Detail

IntroSorter

public IntroSorter()

Create a new IntroSorter.

Method Detail

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

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 slot i so that it can later be used as a pivot, see Sorter.comparePivot(int).

Overrides:

setPivot in class Sorter

comparePivot

protected abstract int comparePivot(int j)

Description copied from class: Sorter

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

Overrides:

comparePivot in class Sorter

compare

protected int compare(int i,
                      int j)

Description copied from class: Sorter

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

Specified by:

compare in class Sorter