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 &amp;&amp; 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] &lt; right[0]) {
        array.push(left.shift());
    } else if (left[0] &gt; right[0]) {
        array.push(right.shift());
    } else {
        array.push(left.shift());
        right.shift();
    }
    return merge(left, right, array);
}

function mergeSort(array){
    if (array.length &gt; 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:


&gt; mergeSort([2, 1, 5]);
[1, 1, 2, 5]

&gt; 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 &amp;&amp; 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] &lt; right[0]) {
        array.push(left.shift());
    } else {
        array.push(right.shift());
    }
    return merge(left, right, array);
}