de.caff.generics.algorithm

Class TimSortFloat

java.lang.Object

de.caff.generics.algorithm.TimSortFloat

public class TimSortFloat
extends java.lang.Object

TimSort for primitive floats.

This is a nearly 1:1 copy of TimSort for objects.

Standard Java can sort primitive float values only in their natural order. This class allows sorting them in any user-defined order.

Having this flexibility comes with a price: TimSortFloat.sort(array, FloatOrdering.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, TimSortDouble, 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(float[] array, FloatOrdering order) Sort a float array in the given order.
static void	sort(float[] array, int start, int len, FloatOrdering order) Sort a part of a float array in the given order.
static void	sort(MutableFloatIndexable elements) Sort the comparable elements of a mutable float indexable in their natural order.
static void	sort(MutableFloatIndexable elements, FloatOrdering order) Sort a mutable float 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
                        float[] array,
                        @NotNull
                        FloatOrdering order)

Sort a float array in the given order.

Parameters:

array - float array ordered by this method

order - order to apply

sort

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

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

Parameters:

array - float 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
                        MutableFloatIndexable elements)

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

Parameters:

elements - elements to sort

sort

public static void sort(@NotNull
                        MutableFloatIndexable elements,
                        @NotNull
                        FloatOrdering order)

Sort a mutable float 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