Merge sort in javascript

Question

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

You realize that you are creating a global sorted variable, right? — thefourtheye
– thefourtheye, Commented Feb 16, 2014 at 3:55
Also all the variables in mergesort are global. Global variables and recursion don't generally mix. — Barmar
– Barmar, Commented Feb 16, 2014 at 3:58
Use var sorted to prevent creating globals. All variables are global by default in JS if you omit the var keyword. — Martin Tournoij
– Martin Tournoij, Commented Feb 16, 2014 at 3:59

thefourtheye · Accepted Answer · 2014-02-16 04:05:41Z

3

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 ]

answered Feb 16, 2014 at 4:05

thefourtheye

241k53 gold badges466 silver badges505 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Merge sort in javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related