What Is Faster - Merge 2 Sorted Arrays Into A Sorted Array W/o Duplicate Values

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

Solution 1:

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();
}

Solution 2:

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.