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.INSERTION_SORT_THRESHOLD
Constructor and Description |
---|
IntroSorter()
Create a new
IntroSorter . |
Modifier and Type | Method and Description |
---|---|
protected abstract int |
comparePivot(int j)
Compare the pivot with the slot at
j , similarly to
compare(i, j) . |
(package private) void |
quicksort(int from,
int to,
int maxDepth) |
protected abstract void |
setPivot(int i)
Save the value at slot
i so that it can later be used as a
pivot, see comparePivot(int) . |
void |
sort(int from,
int to)
Sort the slice which starts at
from (inclusive) and ends at
to (exclusive). |
binarySort, binarySort, checkRange, compare, doRotate, heapChild, heapify, heapParent, heapSort, insertionSort, lower, lower2, mergeInPlace, reverse, rotate, siftDown, swap, upper, upper2
public IntroSorter()
IntroSorter
.public final void sort(int from, int to)
Sorter
from
(inclusive) and ends at
to
(exclusive).void quicksort(int from, int to, int maxDepth)
protected abstract void setPivot(int i)
i
so that it can later be used as a
pivot, see comparePivot(int)
.protected abstract int comparePivot(int j)
j
, similarly to
compare(i, j)
.