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 ranges are sorted with insertion sort.
This sort algorithm is fast on most data shapes, especially with low cardinality. If the data
to sort is known to be strictly ascending or descending, prefer TimSorter
.
Constructor and Description |
---|
IntroSorter()
Create a new
IntroSorter . |
Modifier and Type | Method and 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) . |
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). |
public IntroSorter()
IntroSorter
.public final void sort(int from, int to)
Sorter
from
(inclusive) and ends at
to
(exclusive).protected abstract void setPivot(int i)
Sorter
i
so that it can later be used as a
pivot, see Sorter.comparePivot(int)
.protected abstract int comparePivot(int j)
Sorter
j
, similarly to
compare(i, j)
.comparePivot
in class Sorter
protected int compare(int i, int j)
Sorter
i
and j
.
The contract for the returned value is the same as
Comparator.compare(Object, Object)
.Copyright © 2000-2021 Apache Software Foundation. All Rights Reserved.