What is faster - merge 2 sorted arrays into a sort

Question

I was trying to figure out which is the fastest way to do the following task:

Write a function that accepts two arrays as arguments - each of which is a sorted, strictly ascending array of integers, and returns a new strictly ascending array of integers which contains all values from both of the input arrays.

Eg. merging [1, 2, 3, 5, 7] and [1, 4, 6, 7, 8] should return [1, 2, 3, 4, 5, 6, 7, 8].

Since I don't have formal programming education, I fint algorithms and complexity a bit alien :) I've came with 2 solutions, but I'm not sure which one is faster.

solution 1 (it actually uses the first array instead of making a new one):

function mergeSortedArrays(a, b) {
  for (let i = 0, bLen = b.length; i < bLen; i++) {
    if (!a.includes(b[i])) {
      a.push(b[i])
    } 
  }
  console.log(a.sort());
}

const foo = [1, 2, 3, 5, 7],
      bar = [1, 4, 6, 7, 8];
mergeSortedArrays(foo, bar);

and solution 2:

function mergeSortedArrays(a, b) {
  let mergedAndSorted = [];

  while(a.length || b.length) {
    if (typeof a[0] === 'undefined') {
      mergedAndSorted.push(b[0]);
      b.splice(0,1);
    } else if (a[0] > b[0]) {
      mergedAndSorted.push(b[0]);
      b.splice(0,1);
    } else if (a[0] < b[0]) {
      mergedAndSorted.push(a[0]);
      a.splice(0,1);
    } else {
      mergedAndSorted.push(a[0]);
      a.splice(0,1);
      b.splice(0,1);
    }
  }
  console.log(mergedAndSorted);
}

const foo = [1, 2, 3, 5, 7],
      bar = [1, 4, 6, 7, 8];
mergeSortedArrays(foo, bar);

Can someone help me with time complexity of both solutions? Also, is there another, faster solution? Should I be using reduce()?

Answer 1

The complexity also depends on the methods that you use in your code.

1) An algorithm commonly used for sorting is Quicksort (introsort as a variation of quicksort).

It has O(n log n) complexity however the worst case may still be O(n^2) in case the input is already sorted. So your solution has O( length(b) + length(a)+length(b) log (length(a)+length(b)) ) runtime complexity.

2) According to this question on the complexity of splice() the javascript function needs O(n) steps at worst (copying all elements to the new array of size n+1). So your second solution takes length of array b multiplied by n steps needed to copy the elements during splice plus the time to push().

For a good solution that works in linear time O(n+m) refer to this Java example and port it (i.e. create an array of size length(a) + length(b) and step via the indeces as shown). Or check out the very tight and even a littler faster implementation below of the answer.

Answer 2

Your first function modifying passed argument and this is bad practice. You can do it in the following way:

function mergeSortedArrays(a, b) {
    return a.concat(b.filter(el => !a.includes(el))).sort();
}