mergeSort algorithm and memory issue in JavaScript

Question

Here's the code I wrote:

function mergeSort(array){
    if(array.length < 2) return array;
    var mid = Math.floor(array.length / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid, array.length);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
    var result = [];
    while (left.length && right.length){
        if(left[0]>right[0]){
            result.push(right[0]);
        } else {
            result.push(left[0]);
        }

    }
    while(left.length){
        result.push(left[0]);
    }
    while(right.length){
        result.push(right[0]);
    }
    return result;
}
array = [1000, -94, -115, 300, 22]
mergeSort(array);

and below is another solution i found online

    function mergeSort (arr) {
    if (arr.length < 2) return arr;

    var mid = Math.floor(arr.length /2);

    return merge(mergeSort(arr.slice(0,mid)),  mergeSort(arr.slice(mid)));
}

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

var test = [-100,3,53,21,4,0];
console.log(mergeSort(test));

in comparison I can't find any significant difference besides some syntax. But for some reason mine code won't run in both chrome dev console and node.js environment. In chrome, it won't return any result and in node.js it gives me

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory Abort trap: 6 Can someone help me understand what is the difference between the two snippet that actually made the difference?

Thanks in advance!

adeneo · Accepted Answer · 2016-11-13 16:27:47Z

2

Think about it, you have an array left and you do

while(left.length){
    result.push(left[0]);
}

left[0] doesn't change the array, it just gets the first item.

The length of left will never change, what you have there is a while loop that goes on as long as the array has a length over zero, and it always will, as the length never changes.
This is a perfect example of an infinite loop, that eventually fills the callstack and errors out, or in older browsers just crashes.

However if you do

while(left.length){
    result.push(left.shift());
}

Array.shift() removes the first item from the array, so at some point the arrays length will be zero, and the loop stops

answered Nov 13, 2016 at 16:27

adeneo

319k29 gold badges410 silver badges392 bronze badges

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

Comments

Luka Lopusina · Accepted Answer · 2016-11-13 16:38:05Z

1

You never move from first element when you are doing merge. Try this code:

function mergeSort(array){
    if(array.length < 2) return array;
    var mid = Math.floor(array.length / 2);
    var a = array.slice(0, mid);
    var b = array.slice(mid);
    return merge(mergeSort(a), mergeSort(b));
}

function merge(a, b){
    var result = [];
    var i = 0;
    var j = 0;
    while (i < a.length && j < b.length){
        if(a[i] < b[j]){
            result.push(a[i]);
            i++;
        } else {
            result.push(b[j]);
            j++;
        }
    }
    while(i < a.length){
        result.push(a[i]);
        i++;
    }
    while(j < b.length){
        result.push(b[j]);
        j++
    }

    return result;
}

array = [1000, -94, -115, 300, 22];
array = mergeSort(array);
console.log(array);

answered Nov 13, 2016 at 16:38

Luka Lopusina

2,6473 gold badges29 silver badges33 bronze badges

2 Comments

Luka Lopusina Over a year ago

@SamHe If you can check answer as correct it would be really helpful :)

Sam He Over a year ago

@ Luka Lopusina ahh, sorry I'm kinda new. Thanks for the reminder!

Collectives™ on Stack Overflow

mergeSort algorithm and memory issue in JavaScript

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related