CODEWITHSUNDEEP
javascript
humanbeing
humanbeing

Reputation: 1697

Merge sort in javascript

I am working through intro to algorithms and translating the pseudocode into a variety of languages for practice.

I am stuck on javascript. I cannot figure out why my merge function is failing and duplicating inputs. Do you know why?

Thank you

function mergesort(a){
    if (a.length <=1) {
        return a;
        }
    mid = Math.round((a.length/2));
    left = a.slice(0, mid);
    right = a.slice(mid);
    console.log(left,right);
    return merge(mergesort(left), mergesort(right));
}

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


a = [234,526,6,3,2,5];
mergesort(a);

Upvotes: 2

Views: 1542

Answers (1)

thefourtheye
thefourtheye

Reputation: 239483

Your algorithm looks fine, the big problem is you are creating global variables. When you create a variable without using var keyword, that variable will become a global variable.

In your case, the first time you are creating a global variable and then on the successive recursive calls, you are not creating new variables, but reassigning to the the same global variables. To fix this problem, simply prefix the variable declarations with var, like this

var mid = Math.round((a.length/2));
var left = a.slice(0, mid);
var right = a.slice(mid);
...
...
...
var sorted = [];

With that change, the result becomes 

[ 2, 3, 5, 6, 234, 526 ]

Upvotes: 3

Related Questions