de.caff.generics.algorithm

Class TimSortDouble

java.lang.Object

de.caff.generics.algorithm.TimSortDouble

public class TimSortDouble
extends java.lang.Object

TimSort for primitive doubles.

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.

Since:

January 12, 2023

Author:

Tim Peters, Rammi (adaptions)

See Also:

TimSort, TimSortFloat, TimSortInt, TimSortLong

Method Summary

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

sort

public static void sort(@NotNull
                        double[] array,
                        @NotNull
                        DoubleOrdering order)

Sort a double array in the given order.

Parameters:

array - double array ordered by this method

order - order to apply

sort

public static void sort(@NotNull
                        double[] array,
                        int start,
                        int len,
                        @NotNull
                        DoubleOrdering order)

Sort a part of a double array in the given order.

Parameters:

array - double array partly ordered by this method

start - start of part of the array which is sorted

len - number of elements which are sorted

order - order to apply

sort

public static void sort(@NotNull
                        MutableDoubleIndexable elements)

Sort the comparable elements of a mutable double indexable in their natural order.

Parameters:

elements - elements to sort

sort

public static void sort(@NotNull
                        MutableDoubleIndexable elements,
                        @NotNull
                        DoubleOrdering order)

Sort a mutable double indexable in the given order.

Parameters:

elements - elements to sort

order - order defined for elements

Throws:

java.lang.IllegalArgumentException - if order fails its invariant

mergeComputeMinrun

static int mergeComputeMinrun(int n)

Compute a good value for the minimum run length. Natural orders shorter than this are boosted artificially via binary insertion. Returns 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.

Parameters:

n - size of remaining run

Returns:

useful value for minimal run length