Merge Sort in JavaScript


Imagine yourself sitting in the first day of a computer science course. At the top of the syllabus is "merge sort," an algorithm to sort an array.

What is merge sort and how does it work?

The basic idea behind merge sort is that it is easier to "merge" two sorted arrays than to sort one unsorted array. The time complexity of the latter is linear.

You must first take the unsorted array and divide it in half to produce two distinct arrays: A and B. Take the first elements of array A and compare it with the first element of array B. The smaller of the two elements should be inserted into the result array.

Assume that the first value that was inserted into the result array belonged to A. The proceeding element in A will be compared with the first item in B, and so on and so forth.

How can we implement it using JavaScript?

The following algorithm is stable as we are preserving the order of items with equal keys, which, just like "quick sort," makes it more preferable over "selection sort."

var mergeSort = function (array) {
// if length of array is 1 or 2 then it is already sorted
// implies that the array of length 0 or 1 is already sorted
if (array.length < 2) return array;

// cut the array in half
var middle = Math.floor(array.length/2);

// the first part of the array
var left = mergeSort(array.slice(0, middle));

// the second part of the array
var right= mergeSort(array.slice(middle));

return merge(left, right);
};

var merge = function (a, b) {
// store the result
var result = [];
// compare
while (a.length > 0 && b.length > 0) {
    if (a[0] < b[0]) {
        result.push(a.shift());
    } else {
        result.push(b.shift());
    }   
}      
return result.concat(a.length? a : b);   
};

Example:

mergeSort([4, 3, 6, 1, 2, 8]);   // --> [1, 2, 3, 4, 6, 8]