Algorithm Action: Merge Sort Part 1

Photo by Noah Windler on Unsplash

Algos, algos, algos: the cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a series of articles titled Algorithm Action.

Today, we’re beginning our exploration of merge sort.

What is it?

Merge sort is a combination of splitting, sorting and merging actions. It works because it exploits the fact that arrays of 0 or 1 element are always sorted. Therefore, by decomposing an array into smaller arrays of 0 to 1 elements, it’s possible to build up a newly sorted array.

But to make it work, let’s take a quick detour to define the helper function we’ll need to make this work.

The Merge Function

In order to implement merge sort, it’s useful to have a function for merging sorted arrays into a larger, sorted array. The function should run in O(n + m) time and O(n+m) space, where n and m are the sizes of the two parameters and it should iterate over each element only once. The function should not modify the parameters passed to it.

Let’s take a look at its pseudocode:

1. Create an empty array and focus on the smallest values in both arrays
2. While i/j have not hit the end of their respective arrays:

a. If the value in the first array is smaller than
the value in the second array, push the value in the first
array into our results and move on to the next value in the
first array

b. If the value in the first array is larger than
the value in the second array, push the value in the second
array into our results and move on to the next value in the
second array

c. Once we exhaust one array, push in all remaining
values from the other array

When we translate the above, we get:

function merge(arr1, arr2){ 
    let results = []; 
    let i = 0; 
    let j = 0; 
    while (i < arr1.length && j < arr2.length) { 
        if (arr2[j] > arr1[i]) {
            results.push[arr1[i]];
            i++;
        } else {
            results.push(arr2[j]);
            j++; 
        }
    }
    while (i < arr1.length) { 
        results.push(arr1[i]); 
        i++
    }
    while (j < arr2.length) { 
        results.push(arr2[j]); 
        j++;
    }
    return results; 
}