超出合并排序调用堆栈

Question

我担心我在这里遗漏了一些非常明显的东西，但我看不到它。运行这在 chrome 控制台和节点 8.4.0 中，mergeSort 导致 RangeError: Maximum call stack size exceeded 对于长度大于 1 的输入数组。合并功能似乎工作正常。这是代码：

"use strict";

function merge(A, B) {
  if (!Array.isArray(A) || !Array.isArray(B)) {
    throw new Error("merge expects both of its arguments to be arrays");
  }

  let result = [];
  let [i, j] = [0, 0];

  while (A[i]) {
    if (B[j]) {
      if (A[i] <= B[j]) {
        result.push(A[i]);
        i++;
      } else {
        while (A[i] >= B[j]) {
          result.push(B[j]);
          j++;
        }
        result.push(A[i]);
        i++;
      }
    } else {
      result.push(A[i]);
      i++;
    }
  }

  while (B[j]) {
    result.push(B[j]);
    j++;
  }

  return result;
}

function mergeSort(A) {
  if (!Array.isArray(A)) {
    throw new Error("mergeSort expects its argument to be an array");
  }

  if (A.length === 1) return A;
  let i = A.slice(Math.floor(A.length / 2));
  let R = A.slice(i);
  let L = A.slice(0, i);
  return merge(mergeSort(R), mergeSort(L));
}

Answer 1

i 不应该是一个数组。你只要

let i = Math.floor(A.length / 2);

而且你的基本情况太严格了，你的函数也会在空数组上无限递归。

超出合并排序调用堆栈

Merge sort call stack exceeded

javascript

sorting

algorithm

recursion

mergesort