Continuing with the theme of my previous post: Studying Comp Sci by Actually Coding, where I built a Bubble Sort and iterative Binary Search in Javascript, I decided to attempt another classic compsci algorithm: the Merge Sort. This is also a relatively "easy" sort function in terms of understanding the general concept, but proved plenty challenging for me to implement from scratch. The part that confused me the most after just watching the animated gif demos and reading high-level descriptions wasn't the recursive sort, it was actually the subsequent merge step and how it specifically functioned. All of the descriptions glossed over that phase as "simply merge the two back together"... well that's not super helpful when you're actually just trying to figure out how to merge two things in the first place! Recursion in programming? cool. Recursive terminology in documentation? uncool.

I started as a I always do... simply throwing around as many console.log() as possible and adding logic step by step to be sure I'm doing what I think I'm doing! One early "gotcha" was that the way this "divide" needs two sub-arrays, as opposed to the way I was doing binary search which technically had three sub-arrays (treating the center element as it's own sub-array). My logic was off as I was defining the "greater than" half sub-array as starting as middleIndex + 1, when it really needed to be simply middleIndex. To test that my recursive sort steps were working, I logged out each step, and then built a fake merge step that simply concatenated the two arrays using the spread operators: let mergedHalves = [...leftHalf, ...rightHalf]. This fake function was helpful because if I had done everything correct in the first step, the entire mergeSort function would break apart the initial array into 1-item sublists, and then rebuild them back in the same order. This was how I discovered my error above, where I was neglecting to included the item at middleIndex.

Once I was sure the recursive sort was working fine, I needed to figure out how the merge step was actually working, and then implement it in JavaScript. I tried to find a more detailed guide that I could study step by step, but without seeing someone's actual solution in JavaScript; I finally landed on the merge sort wikipedia page which had a detailed pseudo-code implementation. This was super helpful (perhaps a little more detailed than I was hoping in terms of challenging myself) and allowed me to create a functioning merge step. If you're curious, I'll detail this merge step below, and not simply gloss over like all of the other write-ups I encountered:

Sort Step: recursiveSort()

1. break apart your array recursively into two pieces (leftHalf and rightHalf in my code) until all you have left are 1-item sub-arrays
2. return the value from each 1-item array

Merge Step: mergeHalves() within recursiveSort()

1. confirm there are items in both the leftHalf and the rightHalf
2. compare the first element from the two halves
3. remove the smaller of the two from its respective half and place in the mergedArray which is collecting the ordered items
4. keep looping back to step 1 until one or both of the half arrays are empty
5. if the halves were unequal in length at the start, one will still have some items left in it; one by one removed the first element of that remaining sub array and push onto your `mergedArray

Here is the JavaScript implementation I ended up with:

const merge = (data) => {
  console.log('_______MERGE SORTING_______');

  /*  */
  /* method to run 2nd, AFTER the recursive splitting down to 1 item sub lists */
  /*  */
  const mergeHalves = (leftHalf, rightHalf) => {
    console.log('***MERGING', leftHalf, rightHalf);

    // array to be filled merged items
    let mergedArray = [];

    // keep looping while both arrays still have items
    while (leftHalf.length && rightHalf.length) {

      // compare first items of both halves, remove the smaller one and place in the merged array
      if (leftHalf[0] <= rightHalf[0]) {
        console.log('LEFT IS SMALLER');
        mergedArray.push(leftHalf.shift());
      } else {
        console.log('RIGHT IS SMALLER');
        mergedArray.push(rightHalf.shift());
      }
    }

    // if the two halves were uneven, merge in the remaining items from the longer half
    while (leftHalf.length) {
      console.log('REMAINING ITEMS IN LEFT HALF', leftHalf);
      mergedArray.push(leftHalf.shift());
    }
    while (rightHalf.length) {
      console.log('REMAINING ITEMS IN right HALF', rightHalf);
      mergedArray.push(rightHalf.shift());
    }

    return mergedArray;
  };

  /*  */
  /* recursively break apart until they are 1 item sublists */
  /*  */
  const recursiveSort = (data) => {
    if (data.length <= 1) {
      //   if (data === undefined || data.length <= 1) {
      console.log('sublist has 1 or 0 items');
      return data;
    }
    // find the middle or just left of middle if even number of elements
    let middleIndex = Math.floor(data.length / 2);

    // recursive call on first half (slice has an exclusive ending index)
    let leftHalf = recursiveSort(data.slice(0, middleIndex));

    // recursive call on second half
    let rightHalf = recursiveSort(data.slice(middleIndex));

    // merge sorted left and rights
    let merged = mergeHalves(leftHalf, rightHalf);
    return merged;
  };

  // initial call of recursive fn
  return recursiveSort(data);
};

Again, actually writing this code from scratch has done more for my understanding than all of the YouTube and Twitter visualizations I had seen to date. Those were certainly helpful to get a baseline of understanding, but implementing it really solidified each single step and the reasons they are important. Add to that little addictive "spark" you get when something you're building finally comes alive and you've got a recipe for success! Speaking of instant gratification, I added in a small command to my code to allow viewing of over 100 items in a console.log array:

const util = require('util');
console.log(util.inspect(dataArray, { maxArrayLength: null }));

Let me know if you've also implemented any comp sci concepts in your favorite language, and what you think I should attempt next; maybe I'll actually do one in Python finally!