private int gallopLeft(T key, T[] array, int idx, int length, int hint,
            Comparator<T> comparator) {        
        int lastOffset = 0;
        int offset = 1;
        if (comparator.compare(key, array[idx + hint]) > 0) {
            /* array[hint] < key -- gallop right, until
             * array[hint + lastOffset] < key <= array[hint + offset]
             */
            int maxOffset = length - hint;
            while (offset < maxOffset && comparator.compare(key, array[idx + hint + offset]) > 0) {
                lastOffset = offset;
                offset = (offset << 1) + 1;
                /* int overflow.
                 * Note: not sure if this can happen, but it's included in both the
                 * original and Java7 TimSort implementations.
                 */
                if (offset <= 0) {
                    offset = maxOffset;
                }
            }
            if (offset > maxOffset) {
                offset = maxOffset;
            }

            // Translate back into offsets relative to idx.
            lastOffset += hint;
            offset += hint;
        } else {
            /* key <= array[hint] -- gallop left, until
             * array[hint - offset] < key <= array[hint - lastOffset]
             */
            int maxOffset = hint + 1;
            while (offset < maxOffset && comparator.compare(key, array[idx + hint - offset]) <= 0) {
                lastOffset = offset;
                offset = (offset << 1) + 1;
                /* int overflow.
                 * Note: not sure if this can happen, but it's included in both the
                 * original and Java7 TimSort implementations.
                 */
                if (offset <= 0) {
                    offset = maxOffset;
                }
            }
            if (offset > maxOffset) {
                offset = maxOffset;
            }

            // Translate back to positive offsets relative to idx.
            int k = lastOffset;
            lastOffset = hint - offset;
            offset = hint - k;
        }        

        /*
         * Now array[idx+lastOffset] < key <= array[idx+offset], so key belongs somewhere
         * to the right of lastOffset but no farther right than offset.  Do a binary
         * search, with invariant array[idx + lastOffset - 1] < key <= array[idx + offset].
         */
        lastOffset++;
        while (lastOffset < offset) {
            int m = lastOffset + ((offset - lastOffset) >>> 1);

            if (comparator.compare(key, array[idx + m]) > 0) {
                lastOffset = m + 1;  // array[idx + m] < key
            } else {
                offset = m;          // key <= array[idx + m]
            }
        }        
        return offset;
    }
Locate the proper position of key in an array; if the array contains an
element equal to key, return the position immediately to the left of the
leftmost equal element. [gallopRight() does the same except returns the
position to the right of the rightmost equal element (if any).]

@param key the key to search
@param array is a sorted array with n elements, starting at array[0]. n
must be > 0.
@param idx the index to start
@param length the length of the run
@param hint is an index at which to begin the search, 0 <= hint < n. The
closer hint is to the final result, the faster this runs.
@param comparator the comparator used to order the range, and to search
@return is the int k in 0..n such that

array[k-1] < key <= array[k]

pretending that *(a-1) is minus infinity and array[n] is plus infinity.
IOW, key belongs at index k; or, IOW, the first k elements of a should
precede key, and the last n-k should follow key.
jme3-core/src/main/java/com/jme3/util/ListSort.java