de.caff.generics.algorithm

Class TimSortLong

java.lang.Object

de.caff.generics.algorithm.TimSortLong

public class TimSortLong
extends java.lang.Object

TimSort for primitive longs.

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

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

Having this flexibility comes with a price: TimSortLong.sort(array, LongOrdering.ASCENDING will give the same result as Arrays.sort(array), but be some 60% to 75% 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, TimSortFloat, TimSortInt

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(long[] array, int start, int len, LongOrdering order) Sort a part of a long array in the given order.
static void	sort(long[] array, LongOrdering order) Sort a long array in the given order.
static void	sort(MutableLongIndexable elements) Sort the comparable elements of a mutable long indexable in their natural order.
static void	sort(MutableLongIndexable elements, LongOrdering order) Sort a mutable long 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
                        long[] array,
                        @NotNull
                        LongOrdering order)

Sort a long array in the given order.

Parameters:

array - long array ordered by this method

order - order to apply

sort

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

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

Parameters:

array - long 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
                        MutableLongIndexable elements)

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

Parameters:

elements - elements to sort

sort

public static void sort(@NotNull
                        MutableLongIndexable elements,
                        @NotNull
                        LongOrdering order)

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