Merge Sort Visualization Visualizing Merge Sort

I find algorithms fascinating. I've recently been focusing on the awesomeness of sorting algorithms. This is no coincidence as I dove head first into a personal project with the aim of accomplishing two things: become familiar with Vue.js and grow a deeper understanding/ appreciation for sorting algorithms.

My idea for this project was to create a sorting algorithm visualizer that displayed the moment to moment operations that occur inside of each algorithm. This absolutely helped me achieve the to goals previously mentioned (utilize Vue.js & learn more sorting algorithms).

While building this visualizer I came across several challenges. The first challenge was simply diving deeper into each algorithm and writing my own version. The next challenge was dissecting each operation in order to pick and choose what I needed to visualize. Several of the algorithms them lent themselves to being slowed down by async/await functionality, flipping some colors and values, and then letting the algorithm do the rest. I go over an example of this with bubble sort in this blog post. However, merge sort was not so straight forward.

If you are not familiar with how merge sort operates check out this blog and my visualizer so we can dive into the killer inner workings of animating this dude.

Cutting to the chase: merge sort has several steps that require recursive function calls, because of this, I found it increasingly difficult to know when and where to pause the code and color and move the data appropriately in order to visualize the algorithm's operations.

In fact, I never got it to work... I would slow one part of the algorithm down to visualize it which would then cause another part of the algorithm to get all jumbled up. I knew I needed another solution. My algorithm worked excellently and sorted data quickly, but I was having a heck of a time trying to visualize any piece of it without messing up its entire functionality.

So, brainstorm, brainstorm, brainstorm... I decided to not change anything about the algorithm. Instead, I would let it run like normal and add another parameter which would take an array that recorded the operations as they happened! In other words: at each operation inside of merge sort I would create an object that would record the current action (comparing or overwriting), the index, and the value of each piece of data being sorted.

Example of one of the objects:

      {
        // record what action was happening
        action: "overwrite",
        // which index it was occurring at
        idx1: k,
        // the value at that index
        value: arrayCopy[i].value,
      }

Because Vue.js cannot pickup on the updating of an array or a property of an object without the calling Vue.set(), I could let my merge sort algorithm run, record each computation in an object, then store that object to my animations array.

Once the merge sort was finished sorting (which is just about instantly) the DOM looked the exact same and I had an array of objects that held the information from each computation.

All I had to do then was iterate over this array of animations and slowly animate these changes using Vue.set() and then voila!

Once my merge sort algorithm ran, I ran this method to visualize each animation on the DOM.

async function animate(animations) {
  for (let todo of animations) {

    if (todo.action === "compare") {
      // changes the color of the two indexes being compared
      let { value: val1, color: col1 } = this.numbers[todo.idx1];
      let { value: val2, color: col2 } = this.numbers[todo.idx2];
      this.$set(this.numbers, todo.idx1, {
        value: val1,
        color: this.compare,
      });
      this.$set(this.numbers, todo.idx2, {
        value: val2,
        color: this.compare,
      });

      // pauses the event loop to better visualize the algo
      await new Promise((resolve) => setTimeout(resolve, 20));

      // changes the colors back to original color
      this.$set(this.numbers, todo.idx1, {
        value: val1,
        color: col1,
      });
      this.$set(this.numbers, todo.idx2, {
        value: val2,
        color: col2,
      });
    } else {
      // pauses the event loop to better visualize the algo
      await new Promise((resolve) => setTimeout(resolve, 20));

      // overwrite idx1 with idx2, change color to sorted
      this.$set(this.numbers, todo.idx1, {
        value: todo.value,
        color: this.sorted,
      });
    }
  }
}

It's no secret that merge sort can be very tricky. There are several ways of implementing it, but an important note is that in order to utilize this visualizing approach it is necessary to record the index of the values that merge sort is manipulating.

That being said, if you ever so slightly have a hankering to tackle a visualizing project, do it! There is so much to learn and appreciate from each algorithm. I hope this has been helpful and interesting. Best of luck and share your sorting visualizations - we'd all love to see them!