OpenJDK 27 · java.util.TimSort · APIdia, the JavaDoc alternative

Modifier and Type	Field and Description
private final T[]	a The array being sorted.
private final Comparator<? super T>	c The comparator for this sort.
private static final int	INITIAL_TMP_STORAGE_LENGTH Maximum initial size of tmp array, which is used for merging.
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.
private static final 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 final int[]	runBase
private final int[]	runLen
private int	stackSize A stack of pending runs yet to be merged.
private T[]	tmp Temp storage for merges.
private int	tmpBase
private int	tmpLen

Access	Constructor and Description
private	TimSort(T[] the array to be sorted a, Comparator<? super T> the comparator to determine the order of the sort c, T[] a workspace array (slice) work, int origin of usable space in work array workBase, int usable size of work array workLen) Creates a TimSort instance to maintain the state of an ongoing sort.

Method Summary

Modifier and Type	Method and Description
private static <T> void	binarySort(T[] the array in which a range is to be sorted a, int the index of the first element in the range to be sorted lo, int the index after the last element in the range to be sorted hi, int the index of the first element in the range that is not already known to be sorted (`lo <= start <= hi`) start, Comparator<? super T> comparator to used for the sort c) Sorts the specified portion of the specified array using a binary insertion sort.
private static <T> int	Returns: the length of the run beginning at the specified position in the specified array countRunAndMakeAscending(T[] the array in which a run is to be counted and possibly reversed a, int index of the first element in the run lo, int index after the last element that may be contained in the run. It is required that `lo < hi`. hi, Comparator<? super T> the comparator to used for the sort 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[]	Returns: tmp, whether or not it grew ensureCapacity(int the minimum required capacity of the tmp array minCapacity) Ensures that the external array tmp has at least the specified number of elements, increasing its size if necessary.
private static <T> int	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. gallopLeft(T the key whose insertion point to search for key, T[] the array in which to search a, int the index of the first element in the range base, int the length of the range; must be > 0 len, int the index at which to begin the search, 0 <= hint < n. The closer hint is to the result, the faster this method will run. hint, Comparator<? super T> the comparator used to order the range, and to search 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	Returns: the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] gallopRight(T the key whose insertion point to search for key, T[] the array in which to search a, int the index of the first element in the range base, int the length of the range; must be > 0 len, int the index at which to begin the search, 0 <= hint < n. The closer hint is to the result, the faster this method will run. hint, Comparator<? super T> the comparator used to order the range, and to search 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 stack index of the first of the two runs to merge 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 index of first element in first run to be merged base1, int length of first run to be merged (must be > 0) len1, int index of first element in second run to be merged (must be aBase + aLen) base2, int length of second run to be merged (must be > 0) 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 index of first element in first run to be merged base1, int length of first run to be merged (must be > 0) len1, int index of first element in second run to be merged (must be aBase + aLen) base2, int length of second run to be merged (must be > 0) len2) Merges two adjacent runs in place, in a stable fashion.
private static int	Returns: the length of the minimum run to be merged minRunLength(int the length of the array to be sorted n) Returns the minimum acceptable run length for an array of the specified length.
private void	pushRun(int index of the first element in the run runBase, int the number of elements in the run runLen) Pushes the specified run onto the pending-run stack.
private static void	reverseRange(Object[] the array in which a range is to be reversed a, int the index of the first element in the range to be reversed lo, int the index after the last element in the range to be reversed hi) Reverse the specified range of the specified array.
pack-priv static <T> void	sort(T[] the array to be sorted a, int the index of the first element, inclusive, to be sorted lo, int the index of the last element, exclusive, to be sorted hi, Comparator<? super T> the comparator to use c, T[] a workspace array (slice) work, int origin of usable space in work array workBase, int usable size of work array workLen) Sorts the given range, using the given workspace array slice for temp storage when possible.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

a	back to summary
private final T[] a The array being sorted.

c	back to summary
private final Comparator<? super T> c The comparator for this sort.

INITIAL_TMP_STORAGE_LENGTH	back to summary
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.

MIN_GALLOP	back to summary
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.

MIN_MERGE back to summary

MIN_MERGE	back to summary
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` 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.

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 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.

minGallop	back to summary
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.

runBase	back to summary
private final int[] runBase

runLen	back to summary
private final int[] runLen

stackSize	back to summary
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.

tmp	back to summary
private T[] tmp Temp storage for merges. A workspace array may optionally be provided in constructor, and if so will be used as long as it is big enough.

tmpBase	back to summary
private int tmpBase

tmpLen	back to summary
private int tmpLen

Constructor Detail

TimSort	back to summary
private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) Creates a TimSort instance to maintain the state of an ongoing sort. Parameters a:T[] the array to be sorted c:Comparator<? super T> the comparator to determine the order of the sort work:T[] a workspace array (slice) workBase:int origin of usable space in work array workLen:int usable size of work array

TimSort

back to summary

private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen)

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

Parameters

a:T[]: the array to be sorted
c:Comparator<? super T>: the comparator to determine the order of the sort
work:T[]: a workspace array (slice)
workBase:int: origin of usable space in work array
workLen:int: usable size of work array

Method Detail

binarySort back to summary

binarySort	back to summary
private static <T> void binarySort(T[] a, int lo, int hi, int start, 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:T[] the array in which a range is to be sorted lo:int the index of the first element in the range to be sorted hi:int the index after the last element in the range to be sorted start:int the index of the first element in the range that is not already known to be sorted (`lo <= start <= hi`) c:Comparator<? super T> comparator to used for the sort Annotations @SuppressWarnings:fallthrough

private static <T> void binarySort(T[] a, int lo, int hi, int start, 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:T[]: the array in which a range is to be sorted
lo:int: the index of the first element in the range to be sorted
hi:int: the index after the last element in the range to be sorted
start:int: the index of the first element in the range that is not already known to be sorted (lo <= start <= hi)
c:Comparator<? super T>: comparator to used for the sort

Annotations

@SuppressWarnings:fallthrough

countRunAndMakeAscending back to summary

countRunAndMakeAscending	back to summary
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 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:T[] the array in which a run is to be counted and possibly reversed lo:int index of the first element in the run hi:int index after the last element that may be contained in the run. It is required that `lo < hi`. c:Comparator<? super T> the comparator to used for the sort Returns:int the length of the run beginning at the specified position in the specified array

private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 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:T[]: the array in which a run is to be counted and possibly reversed
lo:int: index of the first element in the run
hi:int: index after the last element that may be contained in the run. It is required that lo < hi.
c:Comparator<? super T>: the comparator to used for the sort

Returns:int

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

ensureCapacity	back to summary
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:int the minimum required capacity of the tmp array Returns:T[] tmp, whether or not it grew

ensureCapacity

back to summary

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:int: the minimum required capacity of the tmp array

Returns:T[]

tmp, whether or not it grew

gallopLeft	back to summary
private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, 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:T the key whose insertion point to search for a:T[] the array in which to search base:int the index of the first element in the range len:int the length of the range; must be > 0 hint:int 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:Comparator<? super T> the comparator used to order the range, and to search Returns:int 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.

gallopLeft

back to summary

private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, 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:T: the key whose insertion point to search for
a:T[]: the array in which to search
base:int: the index of the first element in the range
len:int: the length of the range; must be > 0
hint:int: 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:Comparator<? super T>: the comparator used to order the range, and to search

Returns:int

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	back to summary
private static <T> int gallopRight(T key, T[] a, int base, int len, int hint, 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:T the key whose insertion point to search for a:T[] the array in which to search base:int the index of the first element in the range len:int the length of the range; must be > 0 hint:int 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:Comparator<? super T> the comparator used to order the range, and to search Returns:int the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]

gallopRight

back to summary

private static <T> int gallopRight(T key, T[] a, int base, int len, int hint, 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:T: the key whose insertion point to search for
a:T[]: the array in which to search
base:int: the index of the first element in the range
len:int: the length of the range; must be > 0
hint:int: 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:Comparator<? super T>: the comparator used to order the range, and to search

Returns:int

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

mergeAt	back to summary
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:int stack index of the first of the two runs to merge

mergeAt

back to summary

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:int: stack index of the first of the two runs to merge

mergeCollapse	back to summary
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. Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, Richard Bubel and Reiner Hahnle, this is fixed with respect to the analysis in "On the Worst-Case Complexity of TimSort" by Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.

mergeCollapse

back to summary

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. Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, Richard Bubel and Reiner Hahnle, this is fixed with respect to the analysis in "On the Worst-Case Complexity of TimSort" by Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.

mergeForceCollapse	back to summary
private void mergeForceCollapse() Merges all runs on the stack until only one remains. This method is called once, to complete the sort.

mergeHi	back to summary
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:int index of first element in first run to be merged len1:int length of first run to be merged (must be > 0) base2:int index of first element in second run to be merged (must be aBase + aLen) len2:int length of second run to be merged (must be > 0)

mergeHi

back to summary

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:int: index of first element in first run to be merged
len1:int: length of first run to be merged (must be > 0)
base2:int: index of first element in second run to be merged (must be aBase + aLen)
len2:int: length of second run to be merged (must be > 0)

mergeLo	back to summary
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:int index of first element in first run to be merged len1:int length of first run to be merged (must be > 0) base2:int index of first element in second run to be merged (must be aBase + aLen) len2:int length of second run to be merged (must be > 0)

mergeLo

back to summary

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:int: index of first element in first run to be merged
len1:int: length of first run to be merged (must be > 0)
base2:int: index of first element in second run to be merged (must be aBase + aLen)
len2:int: length of second run to be merged (must be > 0)

minRunLength back to summary

minRunLength	back to summary
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`. 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:int the length of the array to be sorted Returns:int the length of the minimum run to be merged

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. 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:int: the length of the array to be sorted

Returns:int

the length of the minimum run to be merged

pushRun	back to summary
private void pushRun(int runBase, int runLen) Pushes the specified run onto the pending-run stack. Parameters runBase:int index of the first element in the run runLen:int the number of elements in the run

pushRun

back to summary

private void pushRun(int runBase, int runLen)

Pushes the specified run onto the pending-run stack.

Parameters

runBase:int: index of the first element in the run
runLen:int: the number of elements in the run

reverseRange	back to summary
private static void reverseRange(Object[] a, int lo, int hi) Reverse the specified range of the specified array. Parameters a:Object[] the array in which a range is to be reversed lo:int the index of the first element in the range to be reversed hi:int the index after the last element in the range to be reversed

reverseRange

back to summary

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

Reverse the specified range of the specified array.

Parameters

a:Object[]: the array in which a range is to be reversed
lo:int: the index of the first element in the range to be reversed
hi:int: the index after the last element in the range to be reversed

sort	back to summary
pack-priv static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) Sorts the given range, using the given workspace array slice for temp storage when possible. This method is designed to be invoked from public methods (in class Arrays) after performing any necessary array bounds checks and expanding parameters into the required forms. Parameters a:T[] the array to be sorted lo:int the index of the first element, inclusive, to be sorted hi:int the index of the last element, exclusive, to be sorted c:Comparator<? super T> the comparator to use work:T[] a workspace array (slice) workBase:int origin of usable space in work array workLen:int usable size of work array Since 1.8

sort

back to summary

pack-priv static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen)

Sorts the given range, using the given workspace array slice for temp storage when possible. This method is designed to be invoked from public methods (in class Arrays) after performing any necessary array bounds checks and expanding parameters into the required forms.

Parameters

a:T[]: the array to be sorted
lo:int: the index of the first element, inclusive, to be sorted
hi:int: the index of the last element, exclusive, to be sorted
c:Comparator<? super T>: the comparator to use
work:T[]: a workspace array (slice)
workBase:int: origin of usable space in work array
workLen:int: usable size of work array

Since

1.8

pack-priv Class TimSort<T>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail