JavaScript: mergeSort возвращает RangeError: превышен максимальный размер стека вызовов

Question

В настоящее время я пытаюсь реализовать mergeSort в Javascript. Я получаю следующую ошибку:

Пользователи / stevenaguilar / Рабочий стол / алгоритмы / слияние / сортировка слиянием. js: 36 сортировка (a, lo, hi) {^ RangeError: Максимальный размер стека вызовов превышено в 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, так как я запускаю 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 проблематично c (правильная формула - lo + (hi - lo) / 2). Добавление lo обратно подсчитывает это дважды. / 2 потенциально дает результат с плавающей точкой, который сломает рекурсивную логику c и потерпит неудачу как индекс.

С точки зрения дизайна, я не думаю, что есть причина делать сортировку слиянием классом с состоянием и создавать экземпляр просто для сортировки массива. Это ненужные накладные расходы, делает вызывающий код многословным и потенциально может привести к ошибкам. Создание методов static имеет больше смысла, предполагая, что вам нужен класс (даже это, вероятно, излишне).

this.aux сохранение между несколькими вызовами методов и вызовами созрело для ошибок и похоже на преждевременную оптимизацию; делая его чисто локальным для метода 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`);