public abstract class TimSorter extends Sorter
Sorter
implementation based on the
TimSort
algorithm.
This implementation is especially good at sorting partially-sorted arrays and sorts small arrays with binary sort.
NOTE:There are a few differences with the original implementation:
maxTempSlots
equal to half of the length of the slice of data to sort.
Modifier and Type | Field and Description |
---|---|
(package private) int |
maxTempSlots |
(package private) static int |
MIN_GALLOP |
(package private) int |
minRun |
(package private) static int |
MINRUN |
(package private) int[] |
runEnds |
(package private) int |
stackSize |
(package private) static int |
STACKSIZE |
(package private) static int |
THRESHOLD |
(package private) int |
to |
BINARY_SORT_THRESHOLD
Modifier | Constructor and Description |
---|---|
protected |
TimSorter(int maxTempSlots)
Create a new
TimSorter . |
Modifier and Type | Method and Description |
---|---|
protected abstract int |
compareSaved(int i,
int j)
Compare element
i from the temporary storage with element
j from the slice to sort, similarly to
Sorter.compare(int, int) . |
protected abstract void |
copy(int src,
int dest)
Copy data from slot
src to slot dest . |
(package private) void |
doRotate(int lo,
int mid,
int hi) |
(package private) void |
ensureInvariants() |
(package private) void |
exhaustStack() |
(package private) int |
lowerSaved(int from,
int to,
int val) |
(package private) int |
lowerSaved3(int from,
int to,
int val) |
(package private) void |
merge(int lo,
int mid,
int hi) |
(package private) void |
mergeAt(int n) |
(package private) void |
mergeHi(int lo,
int mid,
int hi) |
(package private) void |
mergeLo(int lo,
int mid,
int hi) |
(package private) static int |
minRun(int length)
Minimum run length for an array of length
length . |
(package private) int |
nextRun()
Compute the length of the next run, make the run sorted and return its
length.
|
(package private) void |
pushRunLen(int len) |
(package private) void |
reset(int from,
int to) |
protected abstract void |
restore(int i,
int j)
Restore element
j from the temporary storage into slot i . |
(package private) int |
runBase(int i) |
(package private) int |
runEnd(int i) |
(package private) int |
runLen(int i) |
protected abstract void |
save(int i,
int len)
Save all elements between slots
i and i+len
into the temporary storage. |
(package private) void |
setRunEnd(int i,
int runEnd) |
void |
sort(int from,
int to)
Sort the slice which starts at
from (inclusive) and ends at
to (exclusive). |
(package private) int |
upperSaved(int from,
int to,
int val) |
(package private) int |
upperSaved3(int from,
int to,
int val) |
binarySort, binarySort, checkRange, compare, comparePivot, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, setPivot, siftDown, swap, upper, upper2
static final int MINRUN
static final int THRESHOLD
static final int STACKSIZE
static final int MIN_GALLOP
final int maxTempSlots
int minRun
int to
int stackSize
int[] runEnds
protected TimSorter(int maxTempSlots)
TimSorter
.maxTempSlots
- the maximum amount of extra memory to run mergesstatic int minRun(int length)
length
.int runLen(int i)
int runBase(int i)
int runEnd(int i)
void setRunEnd(int i, int runEnd)
void pushRunLen(int len)
int nextRun()
void ensureInvariants()
void exhaustStack()
void reset(int from, int to)
void mergeAt(int n)
void merge(int lo, int mid, int hi)
public void sort(int from, int to)
Sorter
from
(inclusive) and ends at
to
(exclusive).void mergeLo(int lo, int mid, int hi)
void mergeHi(int lo, int mid, int hi)
int lowerSaved(int from, int to, int val)
int upperSaved(int from, int to, int val)
int lowerSaved3(int from, int to, int val)
int upperSaved3(int from, int to, int val)
protected abstract void copy(int src, int dest)
src
to slot dest
.protected abstract void save(int i, int len)
i
and i+len
into the temporary storage.protected abstract void restore(int i, int j)
j
from the temporary storage into slot i
.protected abstract int compareSaved(int i, int j)
i
from the temporary storage with element
j
from the slice to sort, similarly to
Sorter.compare(int, int)
.