de.caff.generics.algorithm

Class TimSortInt

java.lang.Object

de.caff.generics.algorithm.TimSortInt

public class TimSortInt
extends java.lang.Object

TimSort for primitive ints.

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

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

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

Sort an int array in the given order.

Parameters:

array - int array ordered by this method

order - order to apply

sort

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

Sort a part of an int array in the given order.

Parameters:

array - int 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
                        MutableIntIndexable elements)

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

Parameters:

elements - elements to sort

sort

public static void sort(@NotNull
                        MutableIntIndexable elements,
                        @NotNull
                        IntOrdering order)

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