# Merge Sort in Javascript

**Posted:**October 16, 2013

**Filed under:**Algorithms, JavaScript Comments Off on 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[0] < B[0] ? [A[0], B[0]] : [B[0], A[0]]) : []; if(B[0]>A[0]) 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[0], 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.

## Recent Comments