Algorithm Action: Merge Sort Part 2

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.

Previously on Algorithm Action…

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!