JavaScript: mergeSort returns RangeError: Maximum call stack size exceeded

Question

我目前正在尝试在 Javascript 中实现 mergeSort。我收到以下错误：

Users/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36 sort(a, lo, hi) { ^ RangeError: Maximum call stack size exceeded at Merge.sort (/Users/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36:7)

输入不是很大，是一个元素，里面有16个元素。

a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A","M", "P", "L", "E"]

我能够使用 Ruby 创建合并排序并且能够对数组进行排序。不知道为什么 JavaScript 会出现上述错误，因为 im 运行 Node v14.0.0 这里是合并排序的实现：

class Merge {
  constructor() {
    this.aux = []
  }

  sortPublic(a) {
    this.sort(a, 0, a.length - 1);
  }

  merge(a, lo, mid, hi) {
    let i = lo
    let j = hi
    var mid = mid + 1

    for(let k = lo; k <= hi; k++) {
     this.aux[k] = a[k]
    }

    for(let k = lo; k <= hi; k++) {
      if(i > mid) {
        a[k] = this.aux[j++]
      }
      else if(j > hi) {
        a[k] = this.aux[i++]
      }
      else if(this.aux[j] < this.aux[i]) {
        a[k] = this.aux[j++]
      }
      else {
        a[k] = this.aux[i++]
      }
    }

  }

  sort(a, lo, hi) {
    if(lo >= hi) { return; }
    var mid = lo + (lo + hi) / 2
    this.sort(a, lo, mid)
    this.sort(a, mid + 1, hi)
    this.merge(a, lo, mid, hi)
  }
}


let mergeSort = new Merge;
console.log(mergeSort)
let a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]

mergeSort.sortPublic(a);

这里有什么问题？

Answer 1

var mid = lo + (lo + hi) / 2 有多个问题。如果你试图防止溢出，lo + hi 是有问题的（正确的公式是 lo + (hi - lo) / 2）。将 lo 加回去会计算两次。 / 2 可能会给出一个浮点数结果，这将破坏递归逻辑并作为索引失败。

在设计方面，我认为没有理由使合并排序成为有状态的 class 并创建一个实例来对数组进行排序。这是不必要的开销，使调用代码冗长并可能引入错误。使方法 static 更有意义，假设你需要一个 class （即使这可能是矫枉过正）。

this.aux 在多个方法调用和调用之间持续存在 bug 的时机已经成熟，感觉像是过早的优化；使其成为 sort 方法的纯本地代码可提高可读性、封装性并确保调用之间没有陈旧数据。是的，为 merge 的每一帧创建一个数组很昂贵，但如果需要优化，可以将合并数组添加到闭包中或作为参数传递。或者可以合并 in place. Then again, Array#sort 如果性能是您的目标，这是更好的选择。

我还发现运行所有使用传统数组长度协议的拆分，其中 lo 到 mid 包含 lo 且不包含 mid 和包含 mid 且不包含 hi 的第二个块更直观。这避免了 mid + 1 和 hi - 1 以及 <= 循环，我发现这更难推理。

class MergeSorter {
  static merge(a, lo, mid, hi) {
    const sorted = [];
    let i = lo;
    let j = mid;
    
    while (i < mid && j < hi) {
      if (a[i] < a[j]) {
        sorted.push(a[i++]); 
      }
      else {
        sorted.push(a[j++]); 
      }
    }
    
    while (i < mid) sorted.push(a[i++]);
    
    for (let i = 0; i < sorted.length; i++) {
      a[lo++] = sorted[i];
    }
  }

  static sort(a, lo=0, hi=a.length) {
    if (lo < hi - 1) {
      const mid = Math.floor((lo + hi) / 2);
      MergeSorter.sort(a, lo, mid);
      MergeSorter.sort(a, mid, hi);
      MergeSorter.merge(a, lo, mid, hi);
    }
  }
}

const a = [..."MERGESORTEXAMPLE"];
MergeSorter.sort(a);
console.log(a.join(""));

const rnd = n => ~~(Math.random() * n);
let passes = 0;
const tests = 10000;

for (let i = 0; i < tests; i++) {
  const a = Array(rnd(25)).fill().map(() => rnd(25));
  const b = a.slice();
  MergeSorter.sort(a);
  b.sort((a, b) => a - b);

  if ("" + a === "" + b) {
    passes++;
  }
}

console.log(`${passes}/${tests} tests passed`);

JavaScript: mergeSort returns RangeError: Maximum call stack size exceeded

JavaScript: mergeSort returns RangeError: Maximum call stack size exceeded

javascript

sorting

algorithm

recursion

mergesort