Блог

Я прохожу этапы создания собственной реализации сортировки слиянием. Он рекурсивный и имеет базовый вариант. Единственное, чего я не сделал, это несовершенное сокращение вдвое массивов, где длина % 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]) в Node:

 > 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
  

Что здесь не так? Как я могу это исправить, чтобы рекурсивная сортировка слиянием не разрушала мой стек?

Вы не вызываете .shift с () помощью — make it .shift() .