How to Merge Two Arrays in JavaScript and Python

If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the Merge Two Arrays algorithm in JavaScript and Python.

This article originally published at jarednielsen.com

How to Code the Merge Two Arrays Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

Understand the problem
Make a plan
Execute the plan
Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN two sorted arrays
WHEN I pass the two arrays to a `merge` function
THEN I am returned one array containing the values of the original two in sequential order

That’s our general outline. We know our input conditions, two sorted arrays, and our output requirements, one array, and our goal is to merge the two original arrays in sequential order.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

Decomposition
Pattern recognition
Abstraction
Algorithm design

The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?

[1], [2]

Let's call these two arrays left and right.

We're going to need to build a new array, so let's call it result.

Here's our pseudocode so far:

INPUT left, right

SET result TO AN EMPTY ARRAY

If the value stored in left is less than the value stored in right, we simply shift the value in left into our result array. Let's pseudocode that...

INPUT left, right

SET result TO AN EMPTY ARRAY 

IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
    SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right

We can use our ELSE to check the opposite, where the first element in right is less than left:

INPUT left, right

SET result TO AN EMPTY ARRAY 

IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
    SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
ELSE 
    SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Will this work? If we step through it, we only shift the first value out of left. We need to iterate, but what approach to iteration do we take?

Because we don't know the size of our two arrays in advance and we are "counting down" until both arrays are empty, let's use a while loop.

While what?

While there are still values to evaluate in left or right.

INPUT left, right

SET result TO AN EMPTY ARRAY 

WHILE THERE ARE VALUES IN left OR right
    IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
        SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
    ELSE 
        SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Let's step through it...

On our first iteration, left is 1 and right is 2. The result of the evaluation in our conditional is that left is less than right, so we shift 1 off left into result.

On the second iteration, left is empty and right is still 2. The result of the evaluation in our conditional is... what?

Well... it depends. If your language is JavaScript, then yes, right, will evaluate as less than an empty array. But if your language is Python, you are going to get an error.

Why?

Types.

JavaScript is weakly typed, meaning we can be sloppy with our operators.

But Python is strongly typed, so type matters and we can't compare a numerical value to an empty error and get the results we expect.

So... what's the solution?

We know we need to compare the values in both arrays. But we now know we only need to compare the values in both arrays when there are values to compare.

Where have we seen this or something like it before?

Conditionals!

And?

Operators!

Let's use the logical operator AND and only compare both arrays if thec ondition evaluates as true. If we add this to our pseudocode...

INPUT left, right

SET result TO AN EMPTY ARRAY 

WHILE THERE ARE VALUES IN left OR right

    IF THERE ARE ELEMENTS IN left AND right
        IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
            SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
        ELSE 
            SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

What do we do when the AND operator does not evluate as true? If it's not true, we check if there are any values in left. Otherwise, we check if there are any values in right. In both cases, we push the value to result.

Here's our complete pseudocode:

INPUT left, right

SET result TO AN EMPTY ARRAY

WHILE THERE ARE ELEMENTS IN left OR right
    IF THERE ARE ELEMENTS IN left AND right
        IF THE FIRST ELEMENT IN left IS LESS THAN THE FIRST ELEMENT IN right
            SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
        ELSE 
            SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left
    ELSE IF
        SHIFT THE FIRST ELEMENT OFF left AND PUSH IT INTO right
    ELSE
        SHIFT THE FIRST ELEMENT OFF right AND PUSH IT INTO left

RETURN result

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Merge Two Arrays Algorithm in JavaScript

Let's start with JavaScript...

const merge = (left, right) => {

    let result = [];

    while(left.length || right.length) {

        if(left.length && right.length) {
            if(left[0] < right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        } else if(left.length) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result;
};

How to Code the Merge Two Arrays Algorithm in Python

Now let's see it in Python...

def merge(left, right):
    result = []

    while (len(left) or len(right)):
        if (len(left) and len(right)):
            if (left[0] < right[0]):
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif (len(left)):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result