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