timsort.js
/**
 * 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.
 * 
 * @param {Object} key 
 * @param {Array} a 
 * @param {Number} base 
 * @param {Number} len 
 * @param {Number} hint 
 * @param {Number} c 
 * @returns {Number}
 */
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.


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 .
function gallopLeft(key, a, base, len, hint, c){
    let lastOfs = 0,
        ofs = 1;
        if (c(key, a[base + hint]) > 0) {
            let maxOfs = len - hint;
            while (ofs < maxOfs && c(key, a[base + hint + ofs]) > 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0){
                    ofs = maxOfs;
                }   
            }
            if (ofs > maxOfs){
                ofs = maxOfs; 
            } 
            lastOfs += hint;
            ofs += hint;
        } else {
            let maxOfs = hint + 1;
            while (ofs < maxOfs && c(key, a[base + hint - ofs]) <= 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0){
                    ofs = maxOfs; 
                } 
            }
            if (ofs > maxOfs){
                ofs = maxOfs;
            } 
            let tmp = lastOfs;
            lastOfs = hint - ofs;
            ofs = hint - tmp;
        }
        lastOfs++;
        while (lastOfs < ofs) {
            let m = lastOfs + ((ofs - lastOfs) >>> 1);
            if (c(key, a[base + m]) > 0){
                lastOfs = m + 1; 
            } else{
                ofs = m;          
            } 
        }
        return ofs;
}
function gallopLeft ( key , a , base , len , hint , c ) { let lastOfs = 0 , ofs = 1 ; if ( c ( key , a [ base + hint ] ) > 0 ) { let maxOfs = len - hint ; while ( ofs < maxOfs && c ( key , a [ base + hint + ofs ] ) > 0 ) { lastOfs = ofs ; ofs = ( ofs << 1 ) + 1 ; if ( ofs <= 0 ) { ofs = maxOfs ; } } if ( ofs > maxOfs ) { ofs = maxOfs ; } lastOfs += hint ; ofs += hint ; } else { let maxOfs = hint + 1 ; while ( ofs < maxOfs && c ( key , a [ base + hint - ofs ] ) <= 0 ) { lastOfs = ofs ; ofs = ( ofs << 1 ) + 1 ; if ( ofs <= 0 ) { ofs = maxOfs ; } } if ( ofs > maxOfs ) { ofs = maxOfs ; } let tmp = lastOfs ; lastOfs = hint - ofs ; ofs = hint - tmp ; } lastOfs ++ ; while ( lastOfs < ofs ) { let m = lastOfs + ( ( ofs - lastOfs ) >>> 1 ) ; if ( c ( key , a [ base + m ] ) > 0 ) { lastOfs = m + 1 ; } else { ofs = m ; } } return ofs ; }
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.
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 .
//assert len > 0 && hint >= 0 && hint < len;
 // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
 // int overflow
 // int overflow
 // Make offsets relative to base
 // key <= a[base + hint]
 // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
 // int overflow
 // Make offsets relative to base
 //assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
 /*
         * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
         * to the right of lastOfs but no farther right than ofs.  Do a binary
         * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
         */ // a[base + m] < key 
 // key <= a[base + m]
 //assert lastOfs == ofs;    // so a[base + ofs - 1] < key <= a[base + ofs]
