javascript - 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 开发控制台和 node.js 环境中运行。在 chrome 中，它不会返回任何结果，在 node.js 中它给我

fatal error :CALL_AND_RETRY_LAST 分配失败 - 进程内存不足中止陷阱:6 有人可以帮助我理解实际产生差异的两个片段之间有什么区别吗？

提前致谢!

Answer 1

想一想，你有一个数组 left 并且你这样做了

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

left[0] 不会更改数组，它只是获取第一项。

left 的长度将永远不会改变，只要数组的长度大于零，就会有一个 while 循环，而且它总是会改变，因为长度永远不会改变。
这是无限循环的完美示例，最终会填充调用堆栈并消除错误，或者在较旧的浏览器中只是崩溃。

但是如果你这样做

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

Array.shift() 删除数组中的第一项，因此在某个时刻数组长度将为零，循环停止