public abstract class MSBRadixSorter extends Sorter
IntroSorter
when the size
of the buckets to sort becomes small. It is NOT stable.
Worst-case memory usage is about 2.3 KB
.Modifier and Type | Field and Description |
---|---|
private int[] |
commonPrefix |
private int[] |
endOffsets |
private static int |
HISTOGRAM_SIZE |
private int[][] |
histograms |
private static int |
LENGTH_THRESHOLD |
private static int |
LEVEL_THRESHOLD |
private int |
maxLength |
BINARY_SORT_THRESHOLD
Modifier | Constructor and Description |
---|---|
protected |
MSBRadixSorter(int maxLength)
Sole constructor.
|
Modifier and Type | Method and Description |
---|---|
private boolean |
assertHistogram(int commonPrefixLength,
int[] histogram) |
private void |
buildHistogram(int from,
int to,
int k,
int[] histogram)
Build an histogram of the k-th characters of values occurring between
offsets
from and to , using getBucket(int, int) . |
protected abstract int |
byteAt(int i,
int k)
Return the k-th byte of the entry at index
i , or -1 if
its length is less than or equal to k . |
protected int |
compare(int i,
int j)
Compare entries found in slots
i and j . |
private int |
computeCommonPrefixLengthAndBuildHistogram(int from,
int to,
int k,
int[] histogram)
Build a histogram of the number of values per
bucket
and return a common prefix length for all visited values. |
private int |
getBucket(int i,
int k)
Return a number for the k-th character between 0 and
HISTOGRAM_SIZE . |
protected Sorter |
getFallbackSorter(int k)
Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal.
|
private void |
introSort(int from,
int to,
int k) |
private void |
radixSort(int from,
int to,
int k,
int l) |
private void |
reorder(int from,
int to,
int[] startOffsets,
int[] endOffsets,
int k)
Reorder based on start/end offsets for each bucket.
|
void |
sort(int from,
int to)
Sort the slice which starts at
from (inclusive) and ends at
to (exclusive). |
private void |
sort(int from,
int to,
int k,
int l) |
private static void |
sumHistogram(int[] histogram,
int[] endOffsets)
Accumulate values of the histogram so that it does not store counts but
start offsets.
|
binarySort, binarySort, checkRange, comparePivot, doRotate, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, setPivot, siftDown, swap, upper, upper2
private static final int LEVEL_THRESHOLD
private static final int HISTOGRAM_SIZE
private static final int LENGTH_THRESHOLD
private final int[][] histograms
private final int[] endOffsets
private final int[] commonPrefix
private final int maxLength
protected MSBRadixSorter(int maxLength)
maxLength
- the maximum length of keys, pass Integer.MAX_VALUE
if unknown.protected abstract int byteAt(int i, int k)
i
, or -1
if
its length is less than or equal to k
. This may only be called
with a value of i
between 0
included and
maxLength
excluded.protected Sorter getFallbackSorter(int k)
protected final int compare(int i, int j)
Sorter
i
and j
.
The contract for the returned value is the same as
Comparator.compare(Object, Object)
.public void sort(int from, int to)
Sorter
from
(inclusive) and ends at
to
(exclusive).private void sort(int from, int to, int k, int l)
private void introSort(int from, int to, int k)
private void radixSort(int from, int to, int k, int l)
k
- the character number to comparel
- the level of recursionprivate boolean assertHistogram(int commonPrefixLength, int[] histogram)
private int getBucket(int i, int k)
HISTOGRAM_SIZE
.private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
bucket
and return a common prefix length for all visited values.buildHistogram(int, int, int, int[])
private void buildHistogram(int from, int to, int k, int[] histogram)
from
and to
, using getBucket(int, int)
.private static void sumHistogram(int[] histogram, int[] endOffsets)
endOffsets
will store the end offsets.private void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k)
startOffsets
- start offsets per bucketendOffsets
- end offsets per bucket