de.ipcon.tools

Class TimSort<T>

java.lang.Object

de.ipcon.tools.TimSort<T>

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

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space. This implementation was adapted from Tim Peters's list sort for Python, which is described in detail here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt Tim's C code may be found here: http://svn.python.org/projects/python/trunk/Objects/listobject.c The underlying techniques are described in this paper (and may have even earlier origins): "Optimistic Sorting and Information Theoretic Complexity" Peter McIlroy SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993. While the API to this class consists solely of static methods, it is (privately) instantiable; a TimSort instance holds the state of an ongoing sort, assuming the input array is large enough to warrant the full-blown TimSort. Small arrays are sorted in place, using a binary insertion sort.

Author:

Josh Bloch Extracted from OpenJDK, sadly necessary as it's completely package private. Only difference is the capability to provide an information about a left 0-n area which is sorted already, to avoid another n sorts.

See Also:

flyingSort(T[], java.util.Comparator<? super T>, int), IntIndexTimSort

Method Summary

Modifier and Type	Method and Description
static <T> void	flyingSort(T[] a, java.util.Comparator<? super T> c, int knownSortedUntil) This method is the core of why I'm extracting TimSort from OpenJDK: It provides a means to start TimSort in a way to avoid a revisiting each and every object first.
static <T> void	sort(T[] a, java.util.Comparator<? super T> c) Sorts a given array $a with the help of the Comparator $c.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

sort

public static <T> void sort(T[] a,
                            java.util.Comparator<? super T> c)

Sorts a given array $a with the help of the Comparator $c.

flyingSort

public static <T> void flyingSort(T[] a,
                                  java.util.Comparator<? super T> c,
                                  int knownSortedUntil)

This method is the core of why I'm extracting TimSort from OpenJDK: It provides a means to start TimSort in a way to avoid a revisiting each and every object first. Given a set of sorted objects $o + a set of yet unsorted objects $n, both combined in one array $a with $o adjacent to $n, one can supply the index of the last element of $o in the combined array as 'knownSortedUntil' into this function. Given a huge number of elements in $o and a small number of elements in $n, this function will avoid the len(o) comparisons being made before checking any elements of n. This accellerates the already very speedy TimSort by factor 3-10 compared to a call of @see sort.

len(o)	len(n)	sort comps	flyingSort comps
1000	10	1170	30-120
1000	100	2500	600-900
1000	1000	11700	9000-10000
10000	10	10200	30-120
10000	100	12000	600-1200
10000	1000	28000	10000-15000
100000	1000	102500	800-1600
1000000	1000	1003500	1000-2500

In short, the flying sort method is never slower (as it _is_ a TimSort still), but for small len(n)/len(o), so a few objects added into a huge amount of already sorted objects, the performance gain can be several orders of magnitude.