2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Using recursion in sort() is fine: n recursive calls to sort() will let you handle an array of length 2n, 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.

\$\endgroup\$
  • \$\begingroup\$ Thanks this is very useful feedback. I have taken your advice and now my solution looks like this: jsbin.com/wiyaja/4/edit \$\endgroup\$ – Paul May 28 '15 at 10:12
  • \$\begingroup\$ Your revised solution isn't quite right — what is parseInt() for? \$\endgroup\$ – 200_success May 28 '15 at 10:26
  • \$\begingroup\$ I've added one more issue to my answer: your mergesort isn't stable. \$\endgroup\$ – 200_success May 28 '15 at 10:26
  • \$\begingroup\$ The parseInt seems unnecessary. And yes I'll change that to make it stable. Thx.. \$\endgroup\$ – Paul May 28 '15 at 11:10
  • 1
    \$\begingroup\$ Final improvement: jsbin.com/wiyaja/7/edit \$\endgroup\$ – Paul May 29 '15 at 0:53
3
\$\begingroup\$

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(n²) 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;
}
\$\endgroup\$
  • \$\begingroup\$ I really like your implementation of the merge function. It's much more distinct and probably also faster. \$\endgroup\$ – Paul May 29 '15 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.