Discussion on: Merging Arrays in Javascript

View post

Another solution, simple and faster.
sort an array
developer.mozilla.org/en-US/docs/W...
concat 2 arrays:
developer.mozilla.org/en-US/docs/W...

Ben Greenberg • Oct 9 '17

Thanks for sharing!

Jan van Brügge • Oct 10 '17 • 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
}

Liam Dalzell-Greenshaw • Oct 10 '17

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.

Jan van Brügge • Oct 10 '17 • 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.

Liam Dalzell-Greenshaw • Oct 10 '17

Absolutely, definitely useful stuff to know!