Merge sort implementation in JS

Question

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;
 }
}

Answer 1

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);
}

• elledienne: 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!