Merge Sort in JavaScript —

Notice the numbered steps. left side then right side.

Lets start with a fancy definition…

“In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.” -Wikipedia

A Comparison based sorting algorithm, meaning we will order elements based on greater than and less than values. Divide and conquer means we will divide the list into smaller chunks before conquering the merge.

So, basically, in a merge sort, you are breaking down your unsorted array into smaller arrays, comparing the values and restructuring the values into a new array that you will return at the end of your algorithm.

so,

Pseudo Steps
//o.)Create a function that will take in an array
//o.)Return a sorted array
//o.) Split our array in half; grab the left half of the array, followed by the right half
//o.) Split down into “single-indexed-arrays”(making names up)// repeat the step above.
//o.) Compare those smallest values and create a new array with sorted values; this can be done with recursion.

So, I’ll post a link below for a visual demonstration; But essentially we are break everything down into pairs you have your left array that will be sorted, and a right side array that will be sorted; inside of each side we are sorting, once sorted we compare the indexes of the sorted Left Side and Right Side and push the values into a new array. this will really click and make sense if you go to https://visualgo.net/bn/sorting and check out their Merge Animation.

We will want to create a helper function, to take care of the comparisons and creating a new array.

first though, this is an example of our mergeSort and merge function. this function was copies off of this article here. I added notation.
https://hackernoon.com/programming-with-js-merge-sort-deb677b777c0

function mergeSort (unsortedArray) {
        if (unsortedArray.length <= 1) {
             return unsortedArray;
        }
        const middle = Math.floor(unsortedArray.length / 2);
        const left = unsortedArray.slice(0, middle);
        const right = unsortedArray.slice(middle);
// Using recursion to combine the left and right
//this is breaking down the left and right side into sorted arrays
// eachtime mergeSort is called in the parameters the left and right // are unique to the side it started on.
        return merge(
            mergeSort(left), 
            mergeSort(right)
            );
}
function merge (left, right) {
        let resultArray =[], leftIndex=0, rightIndex=0;
//Here are are looping through our arrays and itterating using 
//closure       
       while (leftIndex < left.length && rightIndex < right.length) {
      //Here we are sorting our arrays by index values and pushing //into our newly created array that will be returned.
        if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
        } else {
        resultArray.push(right[rightIndex]);
        rightIndex++;
      }
  }
//Note; you could just return the result array, I did this for console.logging purposes for a better understanding of the code.
//result array is adding the left and right to its value.
     let target = resultArray
                  .concat(left.slice(leftIndex))
                  .concat(right.slice(rightIndex));
     return target;
}

In our mergeSort we are calling the merge function what will take in the values of the mergeSort function by passing in the divided arrays. This is recursion, and is somewhat confusing, i recommend copying this code into your IDE and console logging different keys and values throughout the code.

I highly recommend checking out the visuals; Merge Sort is simple by nature but requires a deeper understanding of closure and recursion; If you have a more efficient way of performing merge sort, please post below; I hope this article helped make merge sort click just a little bit more; One day at a time. These articles are to help me learn to articulate and understand what is going on throughout the Algorithm.

Questions, comments, concerns, Drop a comment below!

you can connect with me on linkedIn at linkedin.com/adanieljohnson