java.lang.Object
org.apache.lucene.util.Sorter
- Direct Known Subclasses:
InPlaceMergeSorter
,IntroSorter
,MSBRadixSorter
,TimSorter
Base class for sorting algorithms implementations.
There are a number of subclasses to choose from that vary in performance and stability. We suggest that you pick the first from this ranked list that meets your requirements:
MSBRadixSorter
for strings (array of bytes/chars). Not a stable sort.StableMSBRadixSorter
for strings (array of bytes/chars). Stable sort.IntroSorter
. Not a stable sort.InPlaceMergeSorter
. When the data to sort is typically small. Stable sort.TimSorter
. Stable sort.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) static final int
(package private) static final int
Below this size threshold, the sub-range is sorted using Insertion sort.private int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) void
binarySort
(int from, int to) A binary sort implementation.(package private) void
binarySort
(int from, int to, int i) (package private) void
checkRange
(int from, int to) protected abstract int
compare
(int i, int j) Compare entries found in slotsi
andj
.protected int
comparePivot
(int j) Compare the pivot with the slot atj
, similarly tocompare(i, j)
.(package private) void
doRotate
(int lo, int mid, int hi) (package private) static int
heapChild
(int from, int i) (package private) void
heapify
(int from, int to) (package private) static int
heapParent
(int from, int i) (package private) void
heapSort
(int from, int to) Use heap sort to sort items betweenfrom
inclusive andto
exclusive.(package private) void
insertionSort
(int from, int to) Sorts between from (inclusive) and to (exclusive) with insertion sort.(package private) int
lower
(int from, int to, int val) (package private) int
lower2
(int from, int to, int val) (package private) void
mergeInPlace
(int from, int mid, int to) (package private) final void
reverse
(int from, int to) (package private) final void
rotate
(int lo, int mid, int hi) protected void
setPivot
(int i) Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.(package private) void
siftDown
(int i, int from, int to) abstract void
sort
(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).protected abstract void
swap
(int i, int j) Swap values at slotsi
andj
.(package private) int
upper
(int from, int to, int val) (package private) int
upper2
(int from, int to, int val)
-
Field Details
-
BINARY_SORT_THRESHOLD
static final int BINARY_SORT_THRESHOLD- See Also:
-
INSERTION_SORT_THRESHOLD
static final int INSERTION_SORT_THRESHOLDBelow this size threshold, the sub-range is sorted using Insertion sort.- See Also:
-
pivotIndex
private int pivotIndex
-
-
Constructor Details
-
Sorter
protected Sorter()Sole constructor, used for inheritance.
-
-
Method Details
-
compare
protected abstract int compare(int i, int j) Compare entries found in slotsi
andj
. The contract for the returned value is the same asComparator.compare(Object, Object)
. -
swap
protected abstract void swap(int i, int j) Swap values at slotsi
andj
. -
setPivot
protected void setPivot(int i) Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
. -
comparePivot
protected int comparePivot(int j) Compare the pivot with the slot atj
, similarly tocompare(i, j)
. -
sort
public abstract void sort(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive). -
checkRange
void checkRange(int from, int to) -
mergeInPlace
void mergeInPlace(int from, int mid, int to) -
lower
int lower(int from, int to, int val) -
upper
int upper(int from, int to, int val) -
lower2
int lower2(int from, int to, int val) -
upper2
int upper2(int from, int to, int val) -
reverse
final void reverse(int from, int to) -
rotate
final void rotate(int lo, int mid, int hi) -
doRotate
void doRotate(int lo, int mid, int hi) -
binarySort
void binarySort(int from, int to) A binary sort implementation. This performsO(n*log(n))
comparisons andO(n^2)
swaps. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort has become less than 20. This algorithm is stable. -
binarySort
void binarySort(int from, int to, int i) -
insertionSort
void insertionSort(int from, int to) Sorts between from (inclusive) and to (exclusive) with insertion sort. Runs inO(n^2)
. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort becomes less than 16. This algorithm is stable. -
heapSort
void heapSort(int from, int to) Use heap sort to sort items betweenfrom
inclusive andto
exclusive. This runs inO(n*log(n))
and is used as a fall-back byIntroSorter
. This algorithm is NOT stable. -
heapify
void heapify(int from, int to) -
siftDown
void siftDown(int i, int from, int to) -
heapParent
static int heapParent(int from, int i) -
heapChild
static int heapChild(int from, int i)
-