squidpony.squidmath

Class TimSort<T>

java.lang.Object

squidpony.squidmath.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.
Most users won't ever need this class directly; its API is meant for implementors of ordered data structures like OrderedMap that allow sorting. In many cases those data structures expose methods like OrderedSet.sort(Comparator) or OrderedMap.sortByValue(Comparator, int, int), and using those class' methods is a much better idea than trying to use TimSort directly on a data structure that already allows sorting.
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.

Method Summary

Modifier and Type	Method and Description
static <T> void	sort(T[] a, IntVLA order, java.util.Comparator<? super T> c) Modifies order by comparing items in the array a with the Comparator c; not likely to be used externally except by code that extends or re-implements SquidLib data structures.
static <T> void	sort(T[] a, IntVLA order, int lo, int hi, java.util.Comparator<? super T> c) Modifies order by comparing items from index lo inclusive to index hi exclusive in the array a with the Comparator c; not likely to be used externally except by code that extends or re-implements SquidLib data structures.

Methods inherited from class java.lang.Object

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

Method Detail

sort

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

Modifies order by comparing items in the array a with the Comparator c; not likely to be used externally except by code that extends or re-implements SquidLib data structures. Generally, order is the OrderedMap.order field or some similar IntVLA used to keep order in an OrderedSet or the like; it will be modified in-place, but the other parameters will be unchanged.

Type Parameters:

T - the type of items in a that c can compare

Parameters:

a - an array of T, where items will be compared using c; will not be modified

order - an IntVLA that stores indices in a in the order they would be iterated through; will be modified

c - a Comparator that can compare items in a

sort

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

Modifies order by comparing items from index lo inclusive to index hi exclusive in the array a with the Comparator c; not likely to be used externally except by code that extends or re-implements SquidLib data structures. Generally, order is the OrderedMap.order field or some similar IntVLA used to keep order in an OrderedSet or the like; it will be modified in-place, but the other parameters will be unchanged.

Type Parameters:

T - the type of items in a that c can compare

Parameters:

a - an array of T, where items will be compared using c; will not be modified

order - an IntVLA that stores indices in a in the order they would be iterated through; will be modified

lo - the inclusive start index to compare in a and change in order

hi - the exclusive end index to compare in a and change in order

c - a Comparator that can compare items in a