Algorithm Action: Merge Sort Part 2

Image for post
Image for post
Photo by Warren Wong 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 wrapping up our exploration of merge sort.

In Part 1 of this series, we explored why we need a helper function to make merge sort work and defined it.

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;
}

Now we’re going to use the above function in the merge sort function, but first let’s check out the pseudocode for the it:

1. Break arrays (and subarrays) into halves using slice() recursively

2. Then, merge smaller sorted arrays into one sorted array

3. Return the newly sorted + merged array

And here’s the code for the merge sort function!

function mergeSort(arr) { 
//we have to use mergeSort recursively,
//so let's start with the base case
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
//call mergeSort on the left and right halves
//of the array
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}

I truly hope this helps you!

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store