JavaScript：mergeSort返回RangeError。超过了最大调用栈大小

Question

我目前正试图用Javascript实现mergeSort。我得到以下错误。

UsersstevenaguilarDesktopalgorithmsmergemerge-sort.js:36 sort(a, lo, hi) { ^ RangeError: Merge.sort处超过了最大调用栈大小(UsersstevenaguilarDesktopalgorithmsmergemerge-sort.js:36:7)

输入没有那么大是一个元素，里面有16个元素。

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

我能够用Ruby创建合并排序，并且能够对数组进行排序。不知道为什么我用JavaScript会出现上述错误，因为我在运行的是 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 有可能给出一个浮动结果，这将打破递归逻辑，作为索引失败。

在设计方面，我认为没有理由让merge sort成为一个有状态的类，并且仅仅为了排序一个数组而创建一个实例。这是不必要的开销，使调用代码变得啰嗦，并有可能引入bug。让方法 static 更有意义，假设你需要一个类（甚至这可能是矫枉过正）。

this.aux 在多个方法调用和调用之间持久化是成熟的bug，而且感觉是过早的优化；把它变成纯本地的 sort 方法提高了可读性、封装性，并确保在调用之间不会有陈旧的数据存留。是的，为每一帧的 merge 是昂贵的，但如果需要优化，可以将合并数组添加到闭包中或作为参数传递。或者合并可以通过以下方式完成 到位. 再来 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`);