Creates a new sorted array with all elements from independently sorted array parameters.

mergeSorted.js

// returns a new sorted array with all elements from independently sorted arrays in arguments[1] thru arguments[n]
function mergeSorted(iterator/* ... arrays */) {
  var result = [],
      arrays = [].slice.call(arguments, 1),
      indexes = [],
      values = [],
      len,
      ix,
      min;

  indexes.length = values.length = len = arrays.length;

  if (!len) return result;
  if (len === 1) return arrays[0].slice(); // always return a new array

  // splice `arrays`, `indexes` and `values`, when indexes[ix] has past end of array

  ix = len;
  while (ix--) {
    indexes[ix] = 0;
    if (arrays[ix].length) {
      values[ix] = iterator(arrays[ix][0]);
      if (ix === len - 1 || values[ix] < min) {
        min = values[ix];
      }
    } else {
      arrays.splice(ix, 1);
      indexes.splice(ix, 1);
      values.splice(ix, 1);
      len--;
    }
  }

  while (len > 1) {

    // yield all values equal to current min
    ix = len;
    while (ix--) {
      while (values[ix] === min) {
        result.push(arrays[ix][indexes[ix]]);
        indexes[ix]++;
        if (indexes[ix] < arrays[ix].length) {
          values[ix] = iterator(arrays[ix][indexes[ix]]);
        } else {
          arrays.splice(ix, 1);
          indexes.splice(ix, 1);
          values.splice(ix, 1);
          len--;
          break; // break; is not strictly necessary here, but avoids a read past end of array
        }
      }
    }

    if (len < 2) break;

    // find next min
    min = values[0];

    ix = len;
    while (ix--) {
      if (values[ix] < min) {
        min = values[ix];
      }
    }
  }

  if (len === 1) {
    result.push.apply(result, arrays[0].slice(indexes[0]));
  }

  return result;
}

usage.js

function demo() {
  var args = [].slice.call(arguments);
  console.log.apply(console, args);
  args.unshift(function(v){return v});
  console.log('result', mergeSorted.apply(null, args));
}

function demo2() {
  var args = [].slice.call(arguments);
  console.log.apply(console, args);
  args.unshift(function(v){return v.v});
  console.log('result', mergeSorted.apply(null, args));
}


demo([]);
demo([1],[1,1,1,1,1,1],[]);
demo([1], [2]);
demo([2], [1]);
demo([2], [1], [3]);
demo([2], [1], [], [3, 4,5,6]);
demo([2,4], [1], [], [3, 4,5,6]);
demo([2,4], [1], [], [3, 4,4,4,4,4,4,4,4,5,6]);


demo2([{v:0}, {v:1}], [{v:0}, {v:1}]);
demo2([{v:0}, {v:1}, {v:1}, {v:1}, {v:1}]);
demo2([]);