loading...

re: Merging Arrays in Javascript VIEW POST

FULL DISCUSSION
 
 
 

Simpler yes, faster no. If you look at algorithmic complexity, the sort() function has at least O(n*log(n)). Presorted merge sort (what this basicly is) has a complexity of O(n).

A canonical implementation would be:

function presortedMergesort(a, b) {
  let p1 = 0, p2 = 0;
  let result = Array(a.length + b.length)

  for(let i = 0; i < result.length; i++) {
    if(b[p2] === undefined || 
      (a[p1] !== undefined && a[p1] <= b[p2])
    ) {
      result[i] = a[p1];
      p1++;
    } else {
      result[i] = b[p2];
      p2++;
    }
  }
  return result;
}

As you can see, only one loop, with n = |a| + |b| executions
}

 

I think that as this is a series for relative beginners, it's important to emphasise the fact that often, simpler code is better than "faster" code. If you're working with arrays as small as in the example, the difference will be essentially negligible.

I usually take the rule that if there is any noticeable slowness in my code, then I go and try and optimise things like this, but in the vast majority of situations (I would suggest), this sort of complexity is overkill.

Yes of course, always write simple first, then measure performance and optimize where needed.
My point was that using properties like presorted arrays can allow you to go beyond the theoretical limit of O(n*log(n)) that a normal sorting algorithmus has.

Absolutely, definitely useful stuff to know!

Code of Conduct Report abuse