为什么这种合并排序实现不起作用？

Question

我第一次用一个辅助数组实现了合并排序，以尝试使用JavaScript实现可视化。这似乎应该是有效的，但它不是。任何帮助或提示将不胜感激。

const merge = (array, auxArray, start, mid, end) => {
  let k = start; 
  let i = start;
  let j = mid + 1;
  while (i <= mid && j <= end) {
    if (auxArray[i] <= auxArray[j]) {
      array[k++] = auxArray[i++];
    } else {
      array[k++] = auxArray[j++];
    }
  }
  while(i <= mid) {
    array[k++] = auxArray[i++];
  }
  while(j <= end) {
    array[k++] = auxArray[j++];
  }
}


const mergeSortHelper = (array, auxArray, start, end) => {
  if (start === end) {
    return;
  }
  let mid = Math.floor((start + end)/2);
  mergeSortHelper(array, auxArray, start, mid);
  mergeSortHelper(array, auxArray, mid + 1, end);
  merge(array, auxArray, start, mid, end);
}


const mergeSort = (array) => {
  let auxArray = array.slice();
  mergeSortHelper(array, auxArray, 0, array.length - 1);
};

编辑：我忘了包括它不起作用的情况。它们是：

输入：[4, 2, 5, 6, 7, 7]输出：[4, 2, 5, 6, 7, 7]

输入：[6,6,6,4,6,2]输出：[4,6,6,6,6,2]

输入：[6, 7, 3, 10, 7, 9, 6, 3, 4, 6]输出：[6, 7, 3, 9, 6, 3, 4, 6, 10, 7]

它对所有大小的数组给出了类似的结果，但对大小为2的数组似乎给出了正确的结果。

在初始化数组（比如a）后，我用mergeSort（a）调用mergeSort函数，然后通过将数组a记录到控制台来检查它是否被排序。数组应该被排序，但它不是。大多数时候数组保持不变，但有时数组略有不同，但没有排序。

Answer 1

考虑排序数组[4,3,2,1]的情况

let array = [4,3,2,1];
mergeSort(array);
    auxArray = <copy of array>
    mergeSortHelper(array, auxArray, 0, 3);
        mergeSortHelper(array, auxArray, 0,1);
            mergeSortHelper(array, auxArray, 0,0); // returns immediately
            mergeSortHelper(array, auxArray, 1,1); // returns immediately
            merge(array, auxArray, 0,1);  // arr[0-1] = {3,4}
        mergeSortHelper(array, auxArray, 2,3);    
            mergeSortHelper(array, auxArray, 0,0); // returns immediately
            mergeSortHelper(array, auxArray, 1,1); // returns immediately
            merge(array, auxArray, 0,1);  // arr[2-3] = {1,2}
        <at this point arr is [3,4,1,2] and auxArray is still [4,3,2,1]
        merge(array, auxArray, 0,1);  // OOPS, you are remerging the junk in auxArray back into array

问题是，当你向下递归时，你会把每个1或2个元素集的排序内容放入arr，但当你向后递归时，你会把auxArray中未排序的内容重新合并到数组中。

简单的解决方法是将array的内容复制回auxArray函数末尾的merge中。

  ...

  while(j <= end) {
    array[k++] = auxArray[j++];
  }

  // ADD THIS LOOP TO THE END OF YOUR merge FUNCTION
  for (t = 0; t < array.length t++) {
     auxArray[t] = array[t];
  }
}

但这里有另一个提示。摆脱auxArray。你不需要它。或者如果你这样做了，只需声明并使用它merge