com.alexkasko.unsafe.offheaplong
public class OffHeapLongSorter extends Object
alexkasko: borrowed from https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java
and adapted to OffHeapLongAddressable
.
This class implements the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
Modifier and Type | Class and Description |
---|---|
private static class |
OffHeapLongSorter.LongComp |
Modifier and Type | Field and Description |
---|---|
private static int |
INSERTION_SORT_THRESHOLD
If the length of an array to be sorted is less than this
constant, insertion sort is used in preference to Quicksort.
|
Constructor and Description |
---|
OffHeapLongSorter() |
Modifier and Type | Method and Description |
---|---|
private static void |
doSort(OffHeapLongAddressable a,
long left,
long right)
Sorts the specified range of the off-heap collection into ascending order.
|
private static void |
doSortWithComparator(OffHeapLongAddressable a,
long left,
long right,
OffHeapLongSorter.LongComp comp)
Sorts the specified range of the off-heap collection into ascending order.
|
private static void |
dualPivotQuicksort(OffHeapLongAddressable a,
long left,
long right)
Sorts the specified range of the off-heap collection into ascending order by the
Dual-Pivot Quicksort algorithm.
|
private static void |
dualPivotQuicksortWithComparator(OffHeapLongAddressable a,
long left,
long right,
OffHeapLongSorter.LongComp comp)
Sorts the specified range of the off-heap collection into ascending order by the
Dual-Pivot Quicksort algorithm.
|
static void |
sort(OffHeapLongAddressable a)
Sorts the specified off-heap collection into ascending order.
|
static void |
sort(OffHeapLongAddressable a,
long fromIndex,
long toIndex)
Sorts the specified range of the off-heap collection into ascending order.
|
static void |
sort(OffHeapLongAddressable a,
long fromIndex,
long toIndex,
OffHeapLongComparator comp)
Sorts the specified range of the off-heap collection into ascending order.
|
static void |
sort(OffHeapLongAddressable a,
OffHeapLongComparator comp)
Sorts the specified off-heap collection into ascending order.
|
private static final int INSERTION_SORT_THRESHOLD
public OffHeapLongSorter()
public static void sort(OffHeapLongAddressable a)
a
- the off-heap collection to be sortedpublic static void sort(OffHeapLongAddressable a, long fromIndex, long toIndex)
fromIndex
, inclusive, to
the index toIndex
, exclusive. If fromIndex == toIndex
,
the range to be sorted is empty (and the call is a no-op).a
- the off-heap collection to be sortedfromIndex
- the index of the first element, inclusive, to be sortedtoIndex
- the index of the last element, exclusive, to be sortedIllegalArgumentException
- if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())
public static void sort(OffHeapLongAddressable a, OffHeapLongComparator comp)
a
- the off-heap collection to be sortedcomp
- comparator that defines sort orderpublic static void sort(OffHeapLongAddressable a, long fromIndex, long toIndex, OffHeapLongComparator comp)
fromIndex
, inclusive, to
the index toIndex
, exclusive. If fromIndex == toIndex
,
the range to be sorted is empty (and the call is a no-op).a
- the off-heap collection to be sortedfromIndex
- the index of the first element, inclusive, to be sortedtoIndex
- the index of the last element, exclusive, to be sortedcomp
- comparator that defines sort orderIllegalArgumentException
- if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())
private static void doSort(OffHeapLongAddressable a, long left, long right)
sort
method in that the
right
index is inclusive, and it does no range checking on
left
or right
.a
- the off-heap collection to be sortedleft
- the index of the first element, inclusive, to be sortedright
- the index of the last element, inclusive, to be sortedprivate static void dualPivotQuicksort(OffHeapLongAddressable a, long left, long right)
a
- the off-heap collection to be sortedleft
- the index of the first element, inclusive, to be sortedright
- the index of the last element, inclusive, to be sortedprivate static void doSortWithComparator(OffHeapLongAddressable a, long left, long right, OffHeapLongSorter.LongComp comp)
sort
method in that the
right
index is inclusive, and it does no range checking on
left
or right
.a
- the off-heap collection to be sortedleft
- the index of the first element, inclusive, to be sortedright
- the index of the last element, inclusive, to be sortedcomp
- comparator that defines sort orderprivate static void dualPivotQuicksortWithComparator(OffHeapLongAddressable a, long left, long right, OffHeapLongSorter.LongComp comp)
a
- the off-heap collection to be sortedleft
- the index of the first element, inclusive, to be sortedright
- the index of the last element, inclusive, to be sortedcomp
- comparator that defines sort orderCopyright © 2014. All Rights Reserved.