Async Binary Insert

async-binary-insert.js

// Insert value into into array (via comparison cb) then call the done cb
var insert = function insert(item, arr, compare, done) {

  if (!done) {
    done = compare;
    compare = false;
  }

  compare = compare || function (a, b, cb) { return cb(a < b); };

  arr = [].slice.call(arr);

  if (!arr.length) return done([item]);

  var pivot = Math.floor(arr.length / 2),
      middle = arr[pivot],
      left = arr.slice(0, pivot),
      right = arr.slice(pivot + 1);

  compare(item, middle, function (result) {
    if (result) {
      right.unshift(middle);
      if (!left.length) { return done([item].concat(right)); }
      insert(item, left, compare, function (result) {
        done(result.concat(right));
      });
    } else {
      left.push(middle);
      if (!right.length) { return done(left.concat(item)); }
      insert(item, right, compare, function (result) {
        done(left.concat(result));
      });
    }
  });
};