How to Merge sorted Arrays in JavaScript

The standard and most understanding code I believe..

function mergeArray(arr1, arr2) {
 var new_array = [];
 var i = 0,
     j = 0,
     index = 0;

 while (new_array.length != (arr1.length + arr2.length) - 1) {
     if (arr1[i] < arr2[j]) {
         new_array.push(arr1[i]);
         i++;
     } else {
         new_array.push(arr2[j]);
         j++;
     }
 }
 return new_array;
}

Function call:

var merged_array = mergeArray([1,6,9,95], [2,7,10,11,14,18]);

The native implementations are not always the fastest (as you may have noticed) and have, historically, been somewhat sluggish, due to extensive error checking. That being said, there may be performance enhancements in the future, due to more robust integration with the hardware or routines specifically built to optimize certain tasks. If you write your own code, your application won't be able to take advantage of these boosts in performance once they're implemented. It's up to you to decide where the advantages lie and what the risks are.

At any rate, I've written a prettier version of your optimized code for funsies:

function mergeSorted(a,b){
    var alen = a.length
      , blen = b.length
      , i, j, k = j = i = 0
      , answer = new Array(alen + blen)
    ;//var

    while(i < alen && j < blen)
                    answer[k++] = a[i].name < b[j].name ? a[i++] : b[j++];
    while(i < alen) answer[k++] = a[i++];
    while(j < blen) answer[k++] = b[j++];

    return answer;
}

Faster, merges in only 1 pass, with more flexibility (keepDuplicates, custom comparator):

/*  mergeSortedArrays(arrays[, keepDuplicates[, comparator[, thisArg]]])
    Merges multiple sorted arrays into a new sorted array.
    Arguments:
        - arrays: array of sorted arrays to be merged
        - keepDuplicates (optional): (true/false) whether to keep duplicate values
            Default: false
        - comparator (optional): function used to compare values
            Default: sort numbers in ascending order
            Example comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
        - thisArg (optional): comparator is bound to thisArg when invoked
    Returns: a new sorted array containing all the values from the arrays
*/
function mergeSortedArrays(arrays, keepDuplicates, comparator, thisArg) {
    // Coerce to boolean to speed up testings in some javascript engines:
    keepDuplicates = !!keepDuplicates;

    // By default, sort numbers in ascending order:
    if(!comparator) comparator = function(a, b) { return a - b; };

    var nb = arrays.length,     // Number of arrays to be merged
        iter = new Array(nb),   // Current position of iteration of each array
        next = [],              // Keep each array sorted by the value of their next element
        length = 0;             // The combined length of all arrays

    // Populate iter and next:
    for(var i = 0, arr; i < nb; i++) {
        arr = arrays[i];
        iter[i] = 0;
        if(arr.length > 0) {
            insertNextIndex(next, i, arr[0], comparator, thisArg);
        }
        length += arr.length;
    }

    // Insert index of array into next:
    function insertNextIndex(next, index, val, comparator, thisArg) {
        var i = next.length;
        while(i--) {    // Reverse loop...
            var j = next[i];
            if(comparator.call(thisArg, arrays[j][iter[j]], val) >= 0) {    // ...until we find a greater value
                break;
            }
        }
        next.splice(i + 1, 0, index);
    }


    var merged = keepDuplicates ? new Array(length) : [],
        k = 0,  // Iterate over merged
        min, val, lastVal;

    // First iteration to get a value for lastVal (for duplicate checks):
    if(!keepDuplicates && next.length > 0) {
        min = next.pop();
        arr = arrays[min];
        i = iter[min]++;
        val = arr[i];
        merged[k++] = val;
        lastVal = val;
        if(++i < arr.length) {  // If available, insert next value in next:
            insertNextIndex(next, min, arr[i], comparator, thisArg);
        }
    }

    // Merge multiple arrays:
    while(next.length > 1) {    // While there is still multiple arrays to be merged
        min = next.pop();
        arr = arrays[min];
        i = iter[min]++;
        val = arr[i];
        if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
            merged[k++] = val;
            lastVal = val;
        }
        if(++i < arr.length) {  // If available, insert next value in next:
            insertNextIndex(next, min, arr[i], comparator, thisArg);
        }
    }

    // When there remain only 1 array with unmerged values, use a faster loop:
    if(next.length > 0) {
        arr = arrays[next[0]];
        i = iter[next[0]];
        length = arr.length;

        while(i < length) { // To the end
            val = arr[i++];
            if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
                merged[k++] = val;
                lastVal = val;
            }
        }
    }

    return merged;
}

Merging in 1 pass eliminates the creation of intermediate arrays which takes time and memory. Also, the number of comparisons is nicely reduced by keeping a sorted list of the next element from each array (see the next array). And when array sizes are known, they are pre-allocated to prevent dynamic re-allocations (though that will depend on your javascript engine).

For your case, I would call it like this:

mergeSortedArrays(arrays, true, function(a, b) {
    return a.name < b.name ? -1 : 1;
});

Note: If you have a large number of arrays you may benefit from using a binary search instead of the linear search in insertNextIndex(). Or from using a Binary Heap for next.

Edited to reflect that Exception's original solution, extended by calling it like mergeSorted(mergeSorted(a,b),c) is faster than my solution here.

Javascript's builtin sort is [not] fast enough that you can just concatenate all the arrays together and sort the entire thing in one go. Javascript is not good for re-implementing things that should be done lower level.

var a1 = [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}]
var a2 = [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}]
var a3 = [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}]

a1.concat(a2,a3).sort(function(a,b){return (a.name>b.name)-(a.name<b.name)})
// [{name:"a"}, {name:"a"}, {name:"b"}, {name:"e"}, {name:"h"}, {name:"i"}, {name:"g"}, {name:"m"}, {name:"m"}, {name:"n"}, {name:"o"}, {name:"x"}]

I like thetheChad's answer but I prefer something more readable

let mergeSorted = function(a, b) {
  let alen = a.length;
  let blen = b.length;
  let i = j = k = 0;
  let sortedNums = new Array(alen + blen);
  while (i < alen && j < blen) {
    if (a[i] < b[j]) {
      sortedNums[k++] = a[i++];
    } else {
      sortedNums[k++] = b[j++];
    }
  }
  while (i < alen) {
    sortedNums[k++] = a[i++];
  }
  while (j < blen) {
    sortedNums[k++] = b[j++];
  }
  return sortedNums;
};

basically mergeSorted allocates memory for a new array the size of the two input arrays combined. Then it populates the destination with items in order. If one of the arrays is longer we while loop until all the items are copied over. Should pass the following test suite.

// test
console.log(mergeSorted([1,6,9,95], [2,7,10,11,14,18]));
console.log(mergeSorted([2,3], [1]))
console.log(mergeSorted([0,0], [0,0]))
console.log(mergeSorted([1,3], [2]))
console.log(mergeSorted([1,2], [3,4]))

If someone is trying this in 2023, this is the simplest way to merge and sort.

const arrayA = [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}];
const arrayB = [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}];
const arrayC = [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}];

function mergeAndSortArrays(...arrays) {
    return arrays.flat().sort((entry1, entry2) => entry1.name.localeCompare(entry2.name));
}

console.log(mergeAndSortArrays(arrayA, arrayB));

Instead of merging a and b, then merging the result with c. There is also the option to keep track of cursors/indexes off all the given collections at once.

For all non-empty collections do:

1. Assign x to the collection with the lowest active value.
2. Add the active value of x to the result.
3. Move the cursor/index of x forward.
4. Remove x from the list of collections if it is done iterating.

const mergeSorted = (function () {
  class ArrayIterator {
    constructor(array) {
      this.array = array;
      this.index = 0;
    }
    next()      { this.index += 1 }
    get done()  { return this.index >= this.array.length }
    get value() { return this.array[this.index] }
  }

  function minIndexBy(array, fn) {
    let minValue, minIndex;
    for (let index = 0; index < array.length; index += 1) {
      const value = fn(array[index]);
      // first iteration always evaluates to `false` (comparison with `undefined`)
      if (value >= minValue) continue;
      minValue = value;
      minIndex = index;
    }
    return minIndex;
  }
  
  return function (...sortedArrays) {
    const iterators = sortedArrays
      .map(array => new ArrayIterator(array))
      .filter(iterator => !iterator.done);
    
    const merged = [];
    while (iterators.length) {
      const index = minIndexBy(iterators, iterator => iterator.value.name);
      const iterator = iterators[index];
      merged.push(iterator.value);
      iterator.next();
      if (!iterator.done) continue;
      iterators.splice(index, 1);
    }
    return merged;
  };
})();

console.log(mergeSorted(
  [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}],
  [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}],
  [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}],
));

Don't know if this is faster than a simple collections.flat().sort(...), if your collections are big enough it might just be. If you have tons of small collections it's probably not, since each collection adds overhead.