# Merge sort implementation in JS

Just for learning and practicing I've created a completely recursive version of the merge sort algorithm.

I've tested it a little bit and it seems working, but I'm quite sure that it can be largely improved. In particular, I'm hating the long if-else conditional inside the sort function. I think it's really bad written but I can't figure out a way to "beautify" the code without using a loop.

function merge(left, right, array){
if (left.length == 0 && right.length == 0) {
return array;
} else if (left.length == 0) {
return array.concat(right);
} else if (right.length == 0) {
return array.concat(left);
} else if (left[0] < right[0]) {
array.push(left.shift());
} else if (left[0] > right[0]) {
array.push(right.shift());
} else {
array.push(left.shift());
right.shift();
}
return merge(left, right, array);
}

function mergeSort(array){
if (array.length > 1) {
return merge(mergeSort(array.slice(0, Math.ceil(array.length/2))),
mergeSort(array.slice(Math.ceil(array.length/2))), []);
} else {
return array;
}
}


### mergeSort([2, 1, 5]) -> [1, 1, 2, 5] ?

You have a bug:

> mergeSort([2, 1, 5]);
[1, 1, 2, 5]

> mergeSort([2, 1, 5, 1, 9]);
[1, 1, 1, 1, 2, 5, 5, 9]


The problem is here:

sort(mergeSort(array.slice(0, Math.ceil(array.length/2))),
mergeSort(array.slice(Math.floor(array.length/2, array.length))), []);


For example for the array [1, 2, 3], the first slice will be [1, 2] and the second will be [2, 3], so 2 gets duplicated. The more ranges you have with odd length, the more duplicates will creep in.

I'm also wondering what was the intention of this:

Math.floor(array.length/2, array.length)
^^^^^^^^^^^^  typo?


It seems that changing the slices to this will fix it:

array.slice(0, Math.ceil(array.length / 2)))
array.slice(Math.ceil(array.length / 2), array.length))


### Naming

The sort method doesn't "sort". It merges. As such, I'd rename it to merge.

### Beauty

i think it's really bad written but i can't figure out a way to "beautify" the code without using a loop

I think it's fine. This is clear, easy to read, not really ugly. But I'd use spaces more generously around parentheses, like this:

function merge(left, right, array){
if (left.length == 0 && right.length == 0) {
return array;
} else if (left.length == 0) {
return array.concat(right);
} else if (right.length == 0) {
return array.concat(left);
} else if (left[0] < right[0]) {
array.push(left.shift());
} else {
array.push(right.shift());
}
return merge(left, right, array);
}

• Thank you @janos! The Math.floor was an error that i've had already fixed but then i shared the wrong version, my fault :). About the bug when inside the array there are duplicates... That's something i forgot to handle, i'll fix it right now! May 24, 2015 at 15:45