# Merge Sort in Javascript

The Merge Sort algorithm is a divide and conquer algorithm and its basic premise is to grab a problem that can be solved recursively and break it down into smaller chunks.  Then put the chunks back together and you will have a solution that grows higher than a linear solution but better than a quadratic solution.  This algorithm was discovered and applied a long time ago but I wrote my own version in JavaScript as a homework assignment for my Algorithms class.

Keep in mind that JavaScript has a sort method already!  It has been in place since ECS1 so this is not an attempt to improve on the solution – it is just an exercise.  I have also done some run time tests and will be plotting those results shortly.  I will also compare my run time results to the native JavaScript implementation (spoiler: the native implementation is faster!) and a Java version of the algorithm by Robert Sedgewick & Kevin Wayne.

The annotated JS code is below:

```/* Merge Sort in Javascript by Carlos Moran */

//mergeSort gets two arrays and returns a sorted array

function mergeSort(A, B) {
var s = A.length;
var t = B.length;
var u = s + t;

var i = 0;
var j = 0;

// if only two values are to be compared then return the sorted array immediately

var C = u == 2 ? (A < B ? [A, B] : [B, A]) : [];
if(B>A) counter++;
if (C.length > 0) return C.slice(0);

//otherwise merge taking into account arrays that have different dimensions i.e. one array has 3 elements, one has 2
for (var m = 0; m < u; m++) {

if (j > (t - 1)) {
C.push(A[i++]);
counter++;
continue;
}
if (i > (s - 1)) {
C.push(B[j++]);
continue;
}

A[i] <= B[j] ? C.push(A[i++]) : C.push(B[j++]);
if(A[i]>B[j]) counter++;

}

return C.slice(0);

}

function splitArray(R) {

//split array in two
var l = R.length;
var n = ~~ (l / 2);

//merge recursively until smallest split is achieved then return merged array
if (n > 0) {

return mergeSort(splitArray(R.slice(0, n)), splitArray(R.slice(n)));
} else {

return mergeSort(R.slice(0, 1), R.slice(1));
}

}

return {ms: M, iterations: counter}; // return first array value and total operations
});```

The test was run on Mocha on my desktop and the run times will be posted in a future post! Meanwhile, you can check my next post which runs a test suite of this algorithm in the browser.