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

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函数，使用mergeSort(a)，然后通过将数组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.

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

  ...

  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

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

Why does this merge sort implementation not work?

javascript

sorting

mergesort