5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
2
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – elledienne May 24 '15 at 15:45

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.