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

    All Methods Static Methods Concrete Methods
    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