MergeSort Algorithmus und Speicherproblem in JavaScript

Question

Hier ist der Code, den ich schrieb:

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

und unten ist eine andere Lösung i

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

im Vergleich online gefunden kann ich keinen signifikanten Unterschied außer einige finden Syntax. Aus irgendeinem Grund wird mein Code nicht sowohl in der Chrome-dev-Konsole als auch in der node.js-Umgebung ausgeführt. In Chrome gibt es kein Ergebnis und in node.js gibt es

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory Abort trap: 6 Kann jemand mir helfen zu verstehen, was ist der Unterschied zwischen den zwei Schnipsel, die tatsächlich den Unterschied gemacht?

Vielen Dank im Voraus!

Answer 1

Sie nie von der ersten Bewegung Element, wenn Sie zusammenführen. Versuchen Sie diesen 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); 

Answer 2

darüber nachdenkt, Sie haben eine Reihe left und Sie tun

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

left[0] nicht das Array ändern, es wird nur das erste Element.

Die Länge left wird nie ändern, was Sie haben, gibt es eine while-Schleife, die so lange geht, wie das Array mit einer Länge über Null hat, und es wird immer, wie die Länge ändert sich nie.
Dies ist ein perfektes Beispiel für eine Endlosschleife, die schließlich den Callstack und Fehler ausfüllt, oder in älteren Browsern einfach abstürzt.

Allerdings, wenn Sie tun

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

Array.shift()aus dem Array das erste Element entfernt, so irgendwann die Arrays Länge Null sein wird, und die Schleife stoppt