DualPivotQuicksort Class
Dual-Pivot Quicksort algorithm.
This class implements the dual-pivot quicksort algorithm as presented in Vladimir Yaroslavskiy's paper.
Some improvements have been copied from Android's implementation.
Static Methods
Code void insertionSort_(List a, int left, int right, int compare(a, b)) #
static void insertionSort_(List a, int left, int right, int compare(a, b)) { for (int i = left + 1; i <= right; i++) { var el = a[i]; int j = i; while ((j > left) && (compare(a[j - 1], el) > 0)) { a[j] = a[j - 1]; j--; } a[j] = el; } }
Code void sort(List a, int compare(a, b)) #
Sorts all elements of the given list a
according to the given
compare
function.
The compare
function takes two arguments x
and y
and returns
-1 if x < y
,
0 if x == y
, and
1 if x > y
.
The function's behavior must be consistent. It must not return different results for the same values.
static void sort(List a, int compare(a, b)) { _doSort(a, 0, a.length - 1, compare); }
Code void sortRange(List a, int from, int to, int compare(a, b)) #
Sorts all elements in the range from
(inclusive) to to
(exclusive)
of the given list a
.
If the given range is invalid an "OutOfRange" error is raised. TODO(floitsch): do we want an error?
See sort
for requirements of the compare
function.
static void sortRange(List a, int from, int to, int compare(a, b)) { if ((from < 0) || (to > a.length) || (to < from)) { throw "OutOfRange"; } _doSort(a, from, to - 1, compare); }