Algorithm: Implement Merge Sort in Javascript

tech Feb 5, 2020

If you are preparing  for interviews or just learning to code you must have bumped into sorting algorithm. Merge sort is one of the many sorting algorithms. It's efficient and handy. In fact when you use the inbuilt sort() function of javascript in Mozilla it uses the Merge Sort algorithm.

Let's start coding!

Recursion

First of, merge sort does use recursive technique. If you are not familiar with it, I highly suggest studying it first because other wise this algorithm would be too complicated.

Merge Sort

Merge sort is a Divide and Conqure algorithm. That means you take an array and cut it up in half and cut those halves into halves and keep doing so until you are left with individual element array. Then you sort it while merging the smaller arrays.

For this algorithm we need two functions. One would be the mergeSort() function and the other will be the merge() function.

function mergeSort(array) {
    if(array.length < 2) return array;
    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle, array.length);

    return merge(mergeSort(left), mergeSort(right));
}

So this is where the recursion is happening. We are calling mergeSort() on each halves. But first let's create our merge() function.

function merge(left, right) {
    const result = [];

    while(left.length && right.length) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while(left.length) result.push(left.shift());
    while(right.length) result.push(right.shift());
}

Now we can print and see.

console.log(mergeSort([5,3,7,10,4,1,5]));

There you go you have successfully sorted your array with the infamous Merge Sort!