Untitled

// insertion sort with bin-search (aka binary sort)
var isort = (function () {
    var sort = function (buf, first, last, cmp) {
        for (var i = first + 1; i < last; i += 1) {
            var point = search(buf, first, i, buf[i], cmp);
            rotate(buf, point, i + 1);
        }
    };

    // binary search for insert point (rightmost)
    // e.g. [2, 4, 6] with 3 => 1
    // e.g. [2, 4, 6] with 4 => 2
    // e.g. [2, 4, 6] with 5 => 2
    // e.g. [2, 4, 6] with 6 => 3
    var search = function (buf, first, last, value, cmp) {
        while (first < last) {
            var mid = (first + last) >> 1;
            if (cmp(value, buf[mid])) {
                last = mid;
            } else {
                first = mid + 1;
            }
        }
        return first;
    };

    var rotate = function (buf, first, last) {
        if (last - first <= 1) return;
        var prev = buf[first];
        for (var pointer = last - 1; pointer > first; pointer -= 1) {
            buf[pointer] = buf[pointer - 1];
        }
        buf[first] = prev;
    };

    var lessThan = function (a, b) {
        return a < b;
    };

    return function isort(buf/*, cmp*/) {
        var cmp = arguments[1] || lessThan;
        sort(buf, 0, buf.length, cmp);
        return buf;
    };
})();


// examples
console.log(isort([]));
console.log(isort([1]));
console.log(isort([1,2]));
console.log(isort([2,1]));
console.log(isort([1,2,3,4,5]));
console.log(isort([5,4,3,2,1]));