Merging Arrays in Javascript

In my next installment of coding concepts for liberal arts programmers (i.e. coders who do not come from a math or science background) we will look at merging sorted arrays in Javascript. A common challenge you will encounter is the presentation of two arrays of sorted integers and the need to merge them together into one large sorted array. How might you do that? Let's take a look at one method.

In our scenario we have two lists of sorted numbers:

let firstList = [4, 6, 8, 9]
let secondList = [2, 3, 5, 7]

Before even beginning to code out our solution, if you were facing this problem in any other context what would you do first? Well, you would probably go about creating a new list taking the smallest number from each list and adding it to your new list. How would we code that? At the outset we'd want to just find the smallest number from each list and then remove it so our original lists get smaller and less complicated as we go forward:

function getSmallestThenRemove(firstList, secondList) {
    let smallestFirstList = firstList[0];
    let smallestSecondList = secondList[0];

    if (smallestFirstList < smallestSecondList) {
        return firstList.shift()
    } else {
        return secondList.shift()
    }
}

In this function we locate the smallest number by referencing the first index place in each existing array and creating two new variables to hold that data. (In another post we will discuss how to implement a similar function with two unsorted arrays.) Then we check which smallest number is smaller. If the first list's smallest number is smaller than the second list's smallest number, we return the first list without that number and, if the opposite is true, we return the second list without its smallest number.

Now that we have a function that finds for us the smallest number, removes it from the list and returns the original list without that smallest number, what do we need to do next?

The next step would be to create another function that calls getSmallestThenRemove() from within itself as it iterates through the two separate arrays, adding each smallest number as they are removed from their original arrays into a new merged array:

function mergeLists(firstList, secondList) {
    let newList = [];
    let iteratedNum;

    while (firstList.length != 0 && secondList.length != 0) {
        let iteratedNum = getSmallestThenRemove(firstList, secondList)
        newList.push(iteratedNum)
    }
    return newList.concat(firstList).concat(secondList)
}

Within the mergeLists() function we are doing several things:

1. We create an empty array, which will be the place our new sorted array will live.
2. We create a variable iteratedNum, which will hold the current number we are working with.
3. We work our way through the original lists until they are empty (!= 0). Each time, we define the value of iteratedNum to be the return value of getSmallestThenRemove() and push that value into our newList.
4. Finally, we return the newList by concatenating the remainder of either firstList or secondList, because once we have worked our way through the function we will be left with one original list that is empty and the other that holds the remainder of our new sorted array.

Thus, returning back to our original two lists, once we run our new function we will return the following:

let firstList = [4, 6, 8, 9]
let secondList = [2, 3, 5, 7]

mergeLists(firstList, secondList)

// [2, 3, 4, 5, 6, 7, 8, 9]

Check back next week for another installment of coding concepts for liberal arts programmers!

Comments

[Elarcis]

You can also make use of ES6 to merge any number of lists in a single call:

function mergeArrays(base, ...arrays) { 
  return base
    .concat(...arrays)
    .sort((a, b) => a - b);
}

Please mind that when using Array.prototype.sort without argument, the sorting is done via Unicode endpoints – pretty much an alphabetical sort, which means that this array:

[1, 8, 11, 10]

will be sorted into this one:

[1, 10, 11, 8]

[Ethan Stewart]

This is a great way to think through and implement the algorithm for solving this problem. This is my take on a simpler, more compact solution using the ES6 spread operator and the built-in sort method on JS arrays:

function mergeLists(firstList, secondList) {
  return [...firstList, ...secondList].sort();
}

If you can't use ES6 for whatever reason, the concat method would allow you to still keep this nice and simple:

function mergeLists(firstList, secondList) {
  return firstList.concat(secondList).sort();
}

[Ben Greenberg]

Those are very compact, love the simplicity of it! My goal in these posts is to breakdown what's happening behind the scenes a bit so I intentionally spell out the steps rather than using a built in method. The idea being that once someone has some idea what's happening "behind the scenes" then they will more fully appreciate a language's built in methods.

[janjuks]

sort() should be sort((a, b) => a - b)
Otherwise, surprise, surprise - [1, 2, 11].sort() -> [1, 11, 2]

[Ethan Stewart]

I forgot about that, good catch!

[Xavier Artot]

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...

[Jan van Brügge]

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]

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]

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]

Absolutely, definitely useful stuff to know!

[Ben Greenberg]

Thanks for sharing!

[Carlos Garcia ★]

Thanks for the article. This is a good lesson on algorithm thinking and building. However, the wording in the next phrase confused me a bit:

...we return the first list without that number and, if the opposite is true, we return the second list without its smallest number...

What it is returning is the smallest number found from the two lists/arrays (the iteratedNum variable would then hold this number), and at the same time modifying the original array to not have that number anymore.

[janjuks]

Tiny little thing - you are hiding iteratedNum by defining it inside and outside while loop.

[Ben Greenberg]

Yes, you are right, thanks for noticing!

[Millard]

Just for fun

let firstList = [4, 6, 8, 9]
let secondList = [2, 3, 5, 7]

`${firstList},${secondList}`.split(",")

[Dmytro Pylypenko]

Really faster will be approach to concat and sort.

[Rattanak Chea]

This works and is quite easy to understand. I just want to add, i prefer a pure function where it does always return what's expected without modifying the inputs.