DEV Community

loading...

Discussion on: Merging Arrays in Javascript

Collapse
jvanbruegge profile image
Jan van Brügge • Edited

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
}

Collapse
lgreensh profile image
Liam Dalzell-Greenshaw

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.

Thread Thread
jvanbruegge profile image
Jan van Brügge • Edited

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.

Thread Thread
lgreensh profile image
Liam Dalzell-Greenshaw

Absolutely, definitely useful stuff to know!