org.infinispan.commons.util

Class TimSort<T>

java.lang.Object

org.infinispan.commons.util.TimSort<T>

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

TimSort, backported from JDK7 sources (build openjdk-7-ea-src-b77-03_dec_2009). Javadocs copied accordingly as well. 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

Field Summary

Fields

Modifier and Type	Field and Description
private T[]	a The array being sorted.
private java.util.Comparator<? super T>	c The comparator for this sort.
private static int	INITIAL_TMP_STORAGE_LENGTH Maximum initial size of tmp array, which is used for merging.
private static int	MIN_GALLOP When we get into galloping mode, we stay there until both runs win less often than MIN_GALLOP consecutive times.
private static int	MIN_MERGE This is the minimum sized sequence that will be merged.
private int	minGallop This controls when we get *into* galloping mode.
private int[]	runBase
private int[]	runLen
private int	stackSize A stack of pending runs yet to be merged.
private T[]	tmp Temp storage for merges.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	TimSort(T[] a, java.util.Comparator<? super T> c) Creates a TimSort instance to maintain the state of an ongoing sort.

Method Summary

Methods

Modifier and Type	Method and Description
private static <T> void	binarySort(T[] a, int lo, int hi, int start, java.util.Comparator<? super T> c) Sorts the specified portion of the specified array using a binary insertion sort.
private static <T> int	countRunAndMakeAscending(T[] a, int lo, int hi, java.util.Comparator<? super T> c) Returns the length of the run beginning at the specified position in the specified array and reverses the run if it is descending (ensuring that the run will always be ascending when the method returns).
private T[]	ensureCapacity(int minCapacity) Ensures that the external array tmp has at least the specified number of elements, increasing its size if necessary.
private static <T> int	gallopLeft(T key, T[] a, int base, int len, int hint, java.util.Comparator<? super T> c) Locates the position at which to insert the specified key into the specified sorted range; if the range contains an element equal to key, returns the index of the leftmost equal element.
private static <T> int	gallopRight(T key, T[] a, int base, int len, int hint, java.util.Comparator<? super T> c) Like gallopLeft, except that if the range contains an element equal to key, gallopRight returns the index after the rightmost equal element.
private void	mergeAt(int i) Merges the two runs at stack indices i and i+1.
private void	mergeCollapse() Examines the stack of runs waiting to be merged and merges adjacent runs until the stack invariants are reestablished: 1.
private void	mergeForceCollapse() Merges all runs on the stack until only one remains.
private void	mergeHi(int base1, int len1, int base2, int len2) Like mergeLo, except that this method should be called only if len1 >= len2; mergeLo should be called if len1 <= len2.
private void	mergeLo(int base1, int len1, int base2, int len2) Merges two adjacent runs in place, in a stable fashion.
private static int	minRunLength(int n) Returns the minimum acceptable run length for an array of the specified length.
private void	pushRun(int runBase, int runLen) Pushes the specified run onto the pending-run stack.
private static void	rangeCheck(int arrayLen, int fromIndex, int toIndex) Checks that fromIndex and toIndex are in range, and throws an appropriate exception if they aren't.
private static void	reverseRange(java.lang.Object[] a, int lo, int hi) Reverse the specified range of the specified array.
static <T> void	sort(T[] a, java.util.Comparator<? super T> c)
static <T> void	sort(T[] a, int lo, int hi, java.util.Comparator<? super T> c)

Methods inherited from class java.lang.Object

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

Field Detail

MIN_MERGE

private static final int MIN_MERGE

This is the minimum sized sequence that will be merged. Shorter sequences will be lengthened by calling binarySort. If the entire array is less than this length, no merges will be performed. This constant should be a power of two. It was 64 in Tim Peter's C implementation, but 32 was empirically determined to work better in this implementation. In the unlikely event that you set this constant to be a number that's not a power of two, you'll need to change the minRunLength(int) computation. If you decrease this constant, you must change the stackLen computation in the TimSort constructor, or you risk an ArrayOutOfBounds exception. See listsort.txt for a discussion of the minimum stack length required as a function of the length of the array being sorted and the minimum merge sequence length.

See Also:

Constant Field Values

a

private final T[] a

The array being sorted.

c

private final java.util.Comparator<? super T> c

The comparator for this sort.

MIN_GALLOP

private static final int MIN_GALLOP

When we get into galloping mode, we stay there until both runs win less often than MIN_GALLOP consecutive times.

See Also:

Constant Field Values

minGallop

private int minGallop

This controls when we get *into* galloping mode. It is initialized to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for random data, and lower for highly structured data.

INITIAL_TMP_STORAGE_LENGTH

private static final int INITIAL_TMP_STORAGE_LENGTH

Maximum initial size of tmp array, which is used for merging. The array can grow to accommodate demand. Unlike Tim's original C version, we do not allocate this much storage when sorting smaller arrays. This change was required for performance.

See Also:

Constant Field Values

tmp

private T[] tmp

Temp storage for merges.

stackSize

private int stackSize

A stack of pending runs yet to be merged. Run i starts at address base[i] and extends for len[i] elements. It's always true (so long as the indices are in bounds) that: runBase[i] + runLen[i] == runBase[i + 1] so we could cut the storage for this, but it's a minor amount, and keeping all the info explicit simplifies the code.

runBase

private final int[] runBase

runLen

private final int[] runLen

Constructor Detail

TimSort

private TimSort(T[] a,
       java.util.Comparator<? super T> c)

Creates a TimSort instance to maintain the state of an ongoing sort.

Parameters:

a - the array to be sorted

c - the comparator to determine the order of the sort

Method Detail

sort

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

sort

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

binarySort

private static <T> void binarySort(T[] a,
                  int lo,
                  int hi,
                  int start,
                  java.util.Comparator<? super T> c)

Sorts the specified portion of the specified array using a binary insertion sort. This is the best method for sorting small numbers of elements. It requires O(n log n) compares, but O(n^2) data movement (worst case). If the initial part of the specified range is already sorted, this method can take advantage of it: the method assumes that the elements from index lo, inclusive, to start, exclusive are already sorted.

Parameters:

a - the array in which a range is to be sorted

lo - the index of the first element in the range to be sorted

hi - the index after the last element in the range to be sorted

start - the index of the first element in the range that is not already known to be sorted (@code lo <= start <= hi}

c - comparator to used for the sort

countRunAndMakeAscending

private static <T> int countRunAndMakeAscending(T[] a,
                               int lo,
                               int hi,
                               java.util.Comparator<? super T> c)

Returns the length of the run beginning at the specified position in the specified array and reverses the run if it is descending (ensuring that the run will always be ascending when the method returns). A run is the longest ascending sequence with: a[lo] <= a[lo + 1] <= a[lo + 2] <= ... or the longest descending sequence with: a[lo] > a[lo + 1] > a[lo + 2] > ... For its intended use in a stable mergesort, the strictness of the definition of "descending" is needed so that the call can safely reverse a descending sequence without violating stability.

Parameters:

a - the array in which a run is to be counted and possibly reversed

lo - index of the first element in the run

hi - index after the last element that may be contained in the run. It is required that @code{lo < hi}.

c - the comparator to used for the sort

Returns:

the length of the run beginning at the specified position in the specified array

reverseRange

private static void reverseRange(java.lang.Object[] a,
                int lo,
                int hi)

Reverse the specified range of the specified array.

Parameters:

a - the array in which a range is to be reversed

lo - the index of the first element in the range to be reversed

hi - the index after the last element in the range to be reversed

minRunLength

private static int minRunLength(int n)

Returns the minimum acceptable run length for an array of the specified length. Natural runs shorter than this will be extended with binarySort(T[], int, int, int, java.util.Comparator<? super T>). Roughly speaking, the computation is: If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). Else if n is an exact power of 2, return MIN_MERGE/2. Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k is close to, but strictly less than, an exact power of 2. For the rationale, see listsort.txt.

Parameters:

n - the length of the array to be sorted

Returns:

the length of the minimum run to be merged

pushRun

private void pushRun(int runBase,
           int runLen)

Pushes the specified run onto the pending-run stack.

Parameters:

runBase - index of the first element in the run

runLen - the number of elements in the run

mergeCollapse

private void mergeCollapse()

Examines the stack of runs waiting to be merged and merges adjacent runs until the stack invariants are reestablished: 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 2. runLen[i - 2] > runLen[i - 1] This method is called each time a new run is pushed onto the stack, so the invariants are guaranteed to hold for i < stackSize upon entry to the method.

mergeForceCollapse

private void mergeForceCollapse()

Merges all runs on the stack until only one remains. This method is called once, to complete the sort.

mergeAt

private void mergeAt(int i)

Merges the two runs at stack indices i and i+1. Run i must be the penultimate or antepenultimate run on the stack. In other words, i must be equal to stackSize-2 or stackSize-3.

Parameters:

i - stack index of the first of the two runs to merge

gallopLeft

private static <T> int gallopLeft(T key,
                 T[] a,
                 int base,
                 int len,
                 int hint,
                 java.util.Comparator<? super T> c)

Locates the position at which to insert the specified key into the specified sorted range; if the range contains an element equal to key, returns the index of the leftmost equal element.

Parameters:

key - the key whose insertion point to search for

a - the array in which to search

base - the index of the first element in the range

len - the length of the range; must be > 0

hint - the index at which to begin the search, 0 <= hint < n. The closer hint is to the result, the faster this method will run.

c - the comparator used to order the range, and to search

Returns:

the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], pretending that a[b - 1] is minus infinity and a[b + n] is infinity. In other words, key belongs at index b + k; or in other words, the first k elements of a should precede key, and the last n - k should follow it.

gallopRight

private static <T> int gallopRight(T key,
                  T[] a,
                  int base,
                  int len,
                  int hint,
                  java.util.Comparator<? super T> c)

Like gallopLeft, except that if the range contains an element equal to key, gallopRight returns the index after the rightmost equal element.

Parameters:

key - the key whose insertion point to search for

a - the array in which to search

base - the index of the first element in the range

len - the length of the range; must be > 0

hint - the index at which to begin the search, 0 <= hint < n. The closer hint is to the result, the faster this method will run.

c - the comparator used to order the range, and to search

Returns:

the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]

mergeLo

private void mergeLo(int base1,
           int len1,
           int base2,
           int len2)

Merges two adjacent runs in place, in a stable fashion. The first element of the first run must be greater than the first element of the second run (a[base1] > a[base2]), and the last element of the first run (a[base1 + len1-1]) must be greater than all elements of the second run. For performance, this method should be called only when len1 <= len2; its twin, mergeHi should be called if len1 >= len2. (Either method may be called if len1 == len2.)

Parameters:

base1 - index of first element in first run to be merged

len1 - length of first run to be merged (must be > 0)

base2 - index of first element in second run to be merged (must be aBase + aLen)

len2 - length of second run to be merged (must be > 0)

mergeHi

private void mergeHi(int base1,
           int len1,
           int base2,
           int len2)

Like mergeLo, except that this method should be called only if len1 >= len2; mergeLo should be called if len1 <= len2. (Either method may be called if len1 == len2.)

Parameters:

base1 - index of first element in first run to be merged

len1 - length of first run to be merged (must be > 0)

base2 - index of first element in second run to be merged (must be aBase + aLen)

len2 - length of second run to be merged (must be > 0)

ensureCapacity

private T[] ensureCapacity(int minCapacity)

Ensures that the external array tmp has at least the specified number of elements, increasing its size if necessary. The size increases exponentially to ensure amortized linear time complexity.

Parameters:

minCapacity - the minimum required capacity of the tmp array

Returns:

tmp, whether or not it grew

rangeCheck

private static void rangeCheck(int arrayLen,
              int fromIndex,
              int toIndex)

Checks that fromIndex and toIndex are in range, and throws an appropriate exception if they aren't.

Parameters:

arrayLen - the length of the array

fromIndex - the index of the first element of the range

toIndex - the index after the last element of the range

Throws:

java.lang.IllegalArgumentException - if fromIndex > toIndex

java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > arrayLen