слиянием алгоритм и память проблема в JavaScript

Question

Вот код, который я написал:

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

и ниже другого решения я нашел в Интернете

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

в сравнении я не могу найти какой-либо существенной разницы, кроме некоторых синтаксис. Но по какой-то причине мой код не будет работать как в chrome dev console, так и в среде node.js. В хром он не вернет никакого результата, а в node.js он даст мне

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory Abort trap: 6 Может кто-нибудь помочь мне понять, в чем разница между двумя фрагментами, которые на самом деле повлияли?

Заранее благодарен!

Answer 1

Вы никогда не перейти от первого когда вы делаете слияние. Попробуйте использовать этот код:

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

Answer 2

Подумайте об этом, у вас есть массив left и вы

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

left[0] не изменяет массив, он просто получает первый элемент.

Длина left будет никогда изменения, что у вас там есть цикл, пока что продолжается до тех пор, пока массив имеет длину свыше нуля, и она всегда будет, как и длина не меняется.
Это прекрасный пример бесконечного цикла, который в конечном итоге заполняет стоп-код и ошибки, или в старых браузерах просто падает.

Однако если вы

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

Array.shift()удаляет первый элемент из массива, так что в какой-то момент длина массива будет равен нулю, и цикл останавливается