Implementing Merge sort in JavaScript

Lately I have been watching and enjoying Tim Roughgarten’s lecture series on algorithms. For those who are unfamiliar with algorithms but want to learn more, I highly recommend viewing Roughgarten’s lectures on the topic and trying to follow along with the readings he assigns.

An algorithm is a procedure for solving a problem in computer science. Some problems that algorithms are well-suited to solve include sorting a list, or finding the shortest path between two points. Other algorithms, like the minimax algorithm, allow computers to play adversarial games like tic-tac-toe or chess against human competitors in a strategic fashion. These are just a few examples of the kinds of problems algorithms can solve and form the basis for why algorithms in general are interesting.

Algorithms are an area of computer science that I have not explored as much as various topics in web development, so I am trying to learn more about them and to challenge myself to understand and implement some classic algorithms using JavaScript. I think that working on these exercises will help me to reason more effectively about programming as well as improve my general competence as a web developer.

Right now I am learning more about a subset of algorithmic approaches to problem-solving which are called “divide-and-conquer” type algorithms. With a “divide-and-conquer” algorithm one typically reduces the initial problem to several smaller sub-problems before applying an algorithm to each sub-problem and then recombining the smaller problems once they have been solved.

An overview of what merge sort is

Merge sort is an example of a divide-and-conquer type sorting-algorithm. The input for merge sort is an array of integers of length n, which needs to be sorted, typically from least to greatest. What merge sort does is it splits the unsorted array into two parts and then you recursively apply merge sort to these sub-arrays to further split the arrays until you are left with a bunch of single-element arrays. Then, you compare single-element arrays to one another before recombining them into a two-element, sorted array (and so on). If you do this repeatedly, eventually you end up with a single, sorted array of length n. Sorting algorithms are surprisingly complicated to grasp at first and I’m still trying to wrap my mind around the intricacies of computer sorting in general, but here is my attempt at implementing merge sort in JavaScript:

var unsortedArr = [340, 1, 3, 3, 76, 23, 4, 12, 122, 7642, 646];

function merge(leftArr, rightArr) {
var sortedArr = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr[0]);
      leftArr = leftArr.slice(1)
   } else {
      sortedArr.push(rightArr[0]);
      rightArr = rightArr.slice(1)
     }
   }
  while (leftArr.length)
    sortedArr.push(leftArr.shift());
  while (rightArr.length)
    sortedArr.push(rightArr.shift());
  return sortedArr;
}
function mergesort(arr) {
  if (arr.length < 2) {
    return arr; }
  else {
    var midpoint = parseInt(arr.length / 2);
    var leftArr   = arr.slice(0, midpoint);
    var rightArr  = arr.slice(midpoint, arr.length);
    return merge(mergesort(leftArr), mergesort(rightArr));
  }
}
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));

This code seems to work for arbitrary arrays of integers, though I’ll admit I haven’t tried running it on large arrays yet and I’m sure there is room for improvement. Something I want to work on moving forward is implementing different sorting algorithms in JS and then using a charting library like D3 with React to show a real-time representation of the different sorting algorithms in action.

As always, any corrections or suggestions for improvement are welcome in the comments.

Kindly hit the little heart if you liked this so others can see it too!