de.caff.generics.algorithm

Class TimSort<T>

java.lang.Object

de.caff.generics.algorithm.TimSort<T>

Type Parameters:

T - type of sorted objects

public class TimSort<T>
extends java.lang.Object

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.

Here the algorithms are based on mutable indexables because this makes implementations for lists, arrays and more work in the same way. Also Ordering is used instead of the standard Comparator to make this more consistent with the sister classes with sort primitive values.

Since:

January 12, 2023

Author:

Tim Peters, Rammi (adaptions)

See Also:

TimSortDouble, 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 <E extends java.lang.Comparable<? super E>> void	sort(MutableIndexable<E> elements) Sort the comparable elements of a mutable indexable in their natural order.
static <E> void	sort(MutableIndexable<E> elements, Ordering<? super E> order) Sort a mutable 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 <E extends java.lang.Comparable<? super E>> void sort(@NotNull
                                                                    MutableIndexable<E> elements)

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

Type Parameters:

E - element type of the indexable

Parameters:

elements - elements to sort

sort

public static <E> void sort(@NotNull
                            MutableIndexable<E> elements,
                            @NotNull
                            Ordering<? super E> order)

Sort a mutable indexable in the given order.

Type Parameters:

E - element type of the indexable

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