这个（部分）MergeSort实现为什么吹出堆栈？

Question

我正在执行制作自己的MergeSort实现的步骤。它是递归的并且有一个基本的例子。我没有做的唯一的事情就是长度为％2！= 0的数组不完美。所以你必须插入2^n长度的数组。我可以稍后解决。但是，当我插入长度为4的数组时，会发生堆栈溢出。为什么？

下面的代码：

function mergeSort(arr){ 
    // step 0 - establish the variables 
    let 
    newArr = [], 
    len = arr.length; 
    // step 1 - divide the problem into smaller parts until no longer possible 
    if(len <= 1){ 
    return arr; 
    } 
    if (len === 2){ 
    newArr = (arr[0] < arr[1]) ? arr : arr.reverse(); 
    } else { 
     let 
     arr1 = arr.slice(0, len/2), 
     arr2 = arr.slice(len/2, len); 

     // step 2 - conquer each small problem 
     arr1 = mergeSort(arr1); 
     arr2 = mergeSort(arr2); 

     // step 3 - bring them back together 
     while(arr1.length > 0 || arr2.length > 0){ 
     if (!arr1[0]){ 
      newArr = [...newArr, ...arr2]; 
      break; 
     } 
     if (!arr2[0]) { 
      newArr = [...newArr, ...arr1]; 
      break; 
     } 
     arr1[0] < arr2[0] ? newArr.push(arr1.shift) : newArr.push(arr2.shift); 
     } 
    } 

    // step 4 - return the new array 
    return newArr; 
} 

这里的堆栈跟踪，当我在节点运行mergeSort([4,3,2,1])：

> mergeSort([1,2,3,4]) 

<--- Last few GCs ---> 

    14198 ms: Mark-sweep 1074.0 (1080.2) -> 862.8 (872.4) MB, 8.8/0.0 ms (+ 515.6 ms in 2 steps since start of marking, biggest step 400.2 ms) [GC interrupt] [GC in old space requested]. 
    14859 ms: Mark-sweep 862.8 (872.4) -> 361.0 (370.6) MB, 185.2/0.0 ms [allocation failure] [GC in old space requested]. 
    15922 ms: Mark-sweep 895.8 (905.4) -> 539.3 (548.8) MB, 201.6/0.0 ms [allocation failure] [GC in old space requested]. 


<--- JS stacktrace ---> 

==== JS stack trace ========================================= 

Security context: 0x186ecb3cfb51 <JS Object> 
    2: mergeSort [/Users/waleo/Projects/algorithms/mergesort.js:~1] [pc=0x8c4e2bbcf4f] (this=0x186ecb3e6ee9 <JS Global Object>,arr=0x3b3bf2463f21 <JS Array[4]>) 
    3: /* anonymous */ [repl:1] [pc=0x8c4e2bba890] (this=0x186ecb3e6ee9 <JS Global Object>) 
    7: /* anonymous */(aka /* anonymous */) [vm.js:22] [pc=0x8c4e2b9eb48] (this=0x186ecb304381 <undefined>) 
    8: sigintHandlersWrap(aka sigint... 

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory 
1: node::Abort() [/usr/local/bin/node] 
2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/usr/local/bin/node] 
3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/local/bin/node] 
4: v8::internal::Heap::AllocateUninitializedFixedArray(int) [/usr/local/bin/node] 
5: v8::internal::Factory::NewUninitializedFixedArray(int) [/usr/local/bin/node] 
6: v8::internal::(anonymous namespace)::FastElementsAccessor<v8::internal::(anonymous namespace)::FastPackedObjectElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)2> >::AddArguments(v8::internal::Handle<v8::internal::JSArray>, v8::internal::Handle<v8::internal::FixedArrayBase>, v8::internal::Arguments*, unsigned int, v8::internal::(anonymous namespace)::Where) [/usr/local/bin/node] 
7: v8::internal::(anonymous namespace)::DoArrayPush(v8::internal::Isolate*, v8::internal::(anonymous namespace)::BuiltinArguments<(v8::internal::BuiltinExtraArguments)0>) [/usr/local/bin/node] 
8: v8::internal::Runtime_ArrayPush(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/bin/node] 
9: 0x8c4e2a079a7 
[1] 65429 abort  node 

有什么不对吗？我怎样才能解决这个问题，使递归mergeSort不会吹我的堆栈？

Answer 1

你不叫.shift与() - 使它.shift()。