public class TimSortDouble
extends java.lang.Object
This is a nearly 1:1 copy of TimSort
for objects.
Standard Java can sort primitive double
values only in their natural order.
This class allows sorting them in any user-defined order.
Having this flexibility comes with a price: TimSortDouble.sort(array, DoubleOrdering.ASCENDING
will give the same result as Arrays.sort(array)
, but be some 50% to 70% slower.
TimSort is an advanced stable sorting algorithm developed by Tim Peters.
This code is a port derived from Python 3.11.1 source code found under
http://svn.python.org/projects/python/trunk/Objects/listobject.c.
TimSort is already included in Java since version 1.7 as a package-private class
under java.util.TimSort
(only for sorting Objects).
The workings of TimSort are described in a paper found under http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
TimSort
,
TimSortFloat
,
TimSortInt
,
TimSortLong
Modifier and Type | Method and Description |
---|---|
(package private) static int |
mergeComputeMinrun(int n)
Compute a good value for the minimum run length.
|
static void |
sort(double[] array,
DoubleOrdering order)
Sort a double array in the given order.
|
static void |
sort(double[] array,
int start,
int len,
DoubleOrdering order)
Sort a part of a double array in the given order.
|
static void |
sort(MutableDoubleIndexable elements)
Sort the comparable elements of a mutable double indexable in their natural order.
|
static void |
sort(MutableDoubleIndexable elements,
DoubleOrdering order)
Sort a mutable double indexable in the given order.
|
public static void sort(@NotNull double[] array, @NotNull DoubleOrdering order)
array
- double array ordered by this methodorder
- order to applypublic static void sort(@NotNull double[] array, int start, int len, @NotNull DoubleOrdering order)
array
- double array partly ordered by this methodstart
- start of part of the array which is sortedlen
- number of elements which are sortedorder
- order to applypublic static void sort(@NotNull MutableDoubleIndexable elements)
elements
- elements to sortpublic static void sort(@NotNull MutableDoubleIndexable elements, @NotNull DoubleOrdering order)
elements
- elements to sortorder
- order defined for elementsjava.lang.IllegalArgumentException
- if order fails its invariantstatic int mergeComputeMinrun(int n)
n
if it is less than MIN_MERGE
because it's too small
for fancy stuff.
See http://svn.python.org/projects/python/trunk/Objects/listsort.txt for more info.
n
- size of remaining run