Beginner implementation of Merge Sort

Question

This is my first time implementing a merge sort (just getting started with algorithms & data structures).

Are there any obvious things I have done wrong?

I am also worried that I have overused recursion, as both the merge & the sort function are recursive.

function sort(array) {
 var len = array.length;
 var middle = Math.floor(len*0.5);
 var left = array.slice(0,middle);
 var right = array.slice(middle, len);
 if (len == 1) {
 return array;
 } else {
 }
 return merge(sort(left), sort(right));
}
function merge(left, right) {
 var a = left.length;
 var b = right.length;
 if (a > 0 && b > 0) {
 if (left[0] > right[0]) {
 return [].concat(left[0], merge(left.slice(1,a), right));
 } else {
 return [].concat(right[0], merge(right.slice(1,b), left));
 }
 } else if (a == 0) {
 return right;
 } else of (b == 0)
 return left;
}
var array = [];
for(var i = 0; i < 20; i++) {
 array.push(Math.round(Math.random() * 100));
}
console.log(array);
console.log(sort(array));

From the feedback in this question, I have improved my solution, which can be found here.

• 200_success: Stack Overflow question based on this code

Answer 1

Using recursion in sort() is fine: n recursive calls to sort() will let you handle an array of length 2ⁿ, so you don't have to worry about too much recursion. However, it would be better if you wrote the recursion in the standard pattern: base case first, then the recursive case otherwise. The base case should include empty arrays.

Array.slice(start) gives you a slice from start to the end of the array.

function sort(array) {
 if (array.length <= 1) {
 return array;
 }
 var middle = Math.floor(array.length / 2);
 var left = array.slice(0, middle);
 var right = array.slice(middle);
 return merge(sort(left), sort(right));
}

On the other hand, merge() should not be written recursively. To obtain a merged array of length n, you'll have to make n recursive calls to merge(), and that could easily result in a stack overflow for a long list. Furthermore, each slice involves copying nearly the entire array, so the algorithm is grossly inefficient. You would be much better off writing merge() using a while or for loop.

One of the advantages of mergesort over other sorting algorithms is that it can be a stable sort — that is, if the input contains two elements, neither of which is larger than the other, then they can appear in the same relative order in the output. For numbers, stability doesn't matter: one 42 is indistinguishable from another 42. However, it would be good practice to write your merge() function so that it is stable anyway. For that to happen, if you encounter a tie between left[l] and right[r], you must prefer to take left[l] first, so you should change if (left[0] > right[0]) to if (left[0] >= right[0]), and you must keep your left and right straight instead of swapping them carelessly when merge() calls itself.

• Paul: Thanks this is very useful feedback. I have taken your advice and now my solution looks like this: jsbin.com/wiyaja/4/edit
• 200_success: Your revised solution isn't quite right — what is parseInt() for?
• 200_success: I've added one more issue to my answer: your mergesort isn't stable.
• Paul: The parseInt seems unnecessary. And yes I'll change that to make it stable. Thx..
• Paul: Final improvement: jsbin.com/wiyaja/7/edit

Answer 2

Using recursion works fine in the sort method. That is a good example of how recursion should be used; it divides the problem into smaller parts and calls itself to solve the parts.

Most of the code goes into the else though:

function sort(array) {
 var len = array.length;
 if (len <= 1) {
 return array;
 } else {
 var middle = Math.floor(len * 0.5);
 var left = array.slice(0, middle);
 var right = array.slice(middle);
 return merge(sort(left), sort(right));
 }
}

The merge function shouldn't be recursive though. For that you will create a lot of intermediate arrays. The number of arrays and the length of the arrays both grow linear to the length of the input, so the execution time grows exponentially to the length of the input (i.e. an O(n2) solution).

Just loop through the items and put the lower item from each array in the result:

function merge(left, right) {
 var a = left.length;
 var b = right.length;
 if (a == 0) return right;
 if (b == 0) return left;
 var result = [], l = 0, r = 0;
 while (l + r < a + b) {
 if (l < a && (r == b || left[l] <= right[r])) {
 result.push(left[l++]);
 } else {
 result.push(right[r++]);
 }
 }
 return result;
}

• Paul: I really like your implementation of the merge function. It's much more distinct and probably also faster.