Boiled down: merge sort w/recursion

In my coding journey, I've encountered recursion many times and can only wrap my head around basic recursion algorithms like factorials and the Fibonacci sequence. When it comes to merge sort, I bang my head against the wall because while I understand the idea of it, when it comes down to the code, it just didn't make sense... until now...

I do feel that with recursion, it's an idea where you understand it better the more you see and work with it.

Merge sort idea

This video explains extremely well how merge sort with recursion works: Harvard CS50x lecture (watch until 1:58:33).

The three basic steps are:

• Sort the left half of the list
• Sort the right half of the list
• Merge sorted halves

Okay, that's a lot of help... how do we sort the thing?!

We use a two-pointer system to compare the left and right halves.

Let's look at the code and then break it down:

function mergeSort(list) {
  if (list.length == 1) { // base case
    return list;
  }

  // Get the midpoint to split the list into halves
  let midpoint = Math.floor(list.length / 2);

  let leftHalf = list.slice(0, midpoint);
  let rightHalf = list.slice(midpoint);

  /* 
  Recursive step which further splits halves down into smaller halves
  until the base case
  */
  let left = mergeSort(leftHalf);
  let right = mergeSort(rightHalf);

  // Left half pointer
  let l = 0;
  // Right half pointer
  let r = 0;
  // List pointer
  let k = 0;

  // Compare values to fill list
  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
        list[k] = left[l]
      l++
      k++
    } else {
        list[k] = right[r];
      r++
      k++
    }
  }

  // This only works when only left half still contains elements
  while (l < left.length) {
      list[k] = left[l];
    l++
    k++
  }
  // This only works when only right half still contains elements
  while (r < right.length) {
      list[k] = right[r];
    r++
    k++
  }

  return list;
}

Break down

Base case

if (list.length == 1) { // base case
  return list;
}

This base case is crucial since it enables the rest of the recursion steps to work. Once we reach the base case, we can build up our sorted list.

Let's use a simple list to think about this: [1, 5, 2, 3]. When we get to the base case, we should have 4 pieces: [1], [5], [2], and [3].

Recursive step (first look)

Now, if we look at the initial left half of [1, 5, 2, 3], we have [1, 5], which is also the step before we get to the base case.

let left = mergeSort(leftHalf); // [1]
let right = mergeSort(rightHalf); // [5]

Now that we have our base cases returned, we can begin to sort them.

Sort

We want to initialize a couple of pointers to help us keep track of elements from each half, and a pointer to keep track of where we are in the unsorted list.

// Left half pointer
let l = 0;
// Right half pointer
let r = 0;
// List pointer
let k = 0;

Now let's sort and merge values into our list:

// Compare values to fill list
while (l < left.length && r < right.length) {
  if (left[l] < right[r]) {
      list[k] = left[l]
    l++
    k++
  } else {
      list[k] = right[r];
    r++
    k++
  }
}

Using our basic example, we are working with [1] (left half) and [5] (right half).

Notice, if we were merging a larger list, we might encounter a scenario where (for argument's sake) all elements from one half go into our list while the other half remains.

This is how we handle that:

while (l < left.length) {
    list[k] = left[l];
  l++
  k++
}

while (r < right.length) {
    list[k] = right[r];
  r++
  k++
}

These loops only run when the pointer hasn't reached the end of its respective half.

Now, our list is equal to [1, 5].

Return and recursive step (second look)

We return this list to the previous recursive step...

Notice that while we've sorted [1, 5] on the left half, the algorithm was also busy sorting the right half, which should be [2, 3].

This is how our code and values look:

let left = mergeSort(leftHalf); // [1,5]
let right = mergeSort(rightHalf); // [2,3]

Now we run through our algorithm to sort and merge these two halves into a bigger list which is our final step, because we get [1, 2, 3, 5].

Time complexity

The time complexity to split our list into halves all the way down to the base case is logn, and the time complexity to merge them all back together is n, which means the time complexity for merge sort is nlogn.

Thoughts

After taking a look at what I've written, I feel like this is what others have written and talked about, also. Haha. But writing this for myself really solidified the idea.

I hope this made some sense, bare with me as I'm still new at writing blogs, and I was never the best at English class.