/datum/sort_instance

Var Details

L

The array being sorted.

associative

whether we are sorting list keys (0: L[i]) or associated values (1: L[L[i]])

cmp

The comparator proc-reference

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.

Proc Details

binarySort

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 in range [lo,start) are already 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

countRunAndMakeAscending

Returns the length of the run beginning at the specified position and reverses the run if it is back-to-front

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.

gallopLeft

Locates the position to insert key within the specified sorted range. If the range contains elements equal to key, this will return the index of the LEFTMOST of those elements.

key the element to be inserted into the sorted range

base the index of the first element of the sorted range

len the length of the sorted range, must be greater than 0

hint the offset from base at which to begin the search, such that 0 <= hint < len; i.e. base <= hint < base+hint

Returns the index at which to insert element 'key'

gallopRight

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

@param key the key whose insertion point to search for

@param a the array in which to search

@param base the index of the first element in the range

@param len the length of the range; must be > 0

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

@param c the comparator used to order the range, and to search

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

mergeAt

Merges the two consecutive 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.

mergeCollapse

Examines the stack of runs waiting to be merged and merges adjacent runs until the stack invariants are reestablished:

runLen[i-3] > runLen[i-2] + runLen[i-1]

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

Merges all runs on the stack until only one remains. Called only once, to finalise the sort

mergeLo

Merges two adjacent runs in-place in a stable fashion. For performance this method should only be called when len1 <= len2!

minRunLength

Returns the minimum acceptable run length for an array of the specified length. Natural runs shorter than this will be extended with binarySort