当数组长度为偶数时，在 mergesort 合并函数中应该做什么，特别是在 size=2 的情况下？

Question

我已经实现了一个 mergesort 合并函数，但是虽然我尽可能地复制了它，但当左、中、右参数为 0,0,1 时，我已经运行解决了这个问题.在这种情况下，逻辑似乎完全被破坏了。当输入数组14,7时，输出14,7。原因是 left==middle 所以它会立即插入。

此处的mergesort函数通过了测试用例，但它只是正在调试的merge函数。

我本以为 0,0,1 是一个无效的参数规范，但是没有，没有其他方法可以传递长度为 2 的数组中的中间元素。

我试图将我的代码基于 https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java

// Takes in an array that has two sorted subarrays,
//  from [p..q] and [q+1..r], and merges the array
var merge = function(array, p, q, r) {
  console.log(array);
  console.log(p);
  console.log(q);
  console.log(r);
  var tmp = {};
  var k = p;
  var middle = q;
  while(p<=middle && q <= r){
    console.log("aaa");
    console.log(array[p]);
    console.log(array[q]);
    console.log("bbb");

    if (array[p] < array[q]){
        tmp[k] = array[p];
        k++;
        p++;
    } else {
        tmp[k] = array[q];
        k++;
        q++;
    }
  }
  while(p<middle){
        //tmp[k] = array[p];
        k++;
    p++;
  }
  while(r >= q){
        //tmp[k] = array[q];
        k++;
    q++;
  }

  for(var i in tmp){
    array[i] = tmp[i];
  }
  console.log(array);
  console.log(tmp);
  console.log("test");
};


// Takes in an array and recursively merge sorts it
var mergeSort = function(array, p, r) {
    var lowerIndex = p;
    var higherIndex = r;
            if (lowerIndex < higherIndex) {
            var middle = Math.floor(lowerIndex + (higherIndex - lowerIndex) / 2);
            // Below step sorts the left side of the array
            mergeSort(array,lowerIndex, middle);
            // Below step sorts the right side of the array
            mergeSort(array,middle + 1, higherIndex);
            // Now merge both sides
            merge(array,lowerIndex, middle, higherIndex);
        }
};

var array = [14, 7, 3, 12, 9, 11, 6, 2];
array = [14, 7];
mergeSort(array, 0, array.length-1);
console.log("Array after sorting: " + array);
//Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);

Answer 1

中间索引必须仅属于其中一个范围。目前，您正在使用 <= 进行比较，因此它属于两者。

在我看来，使用更常见的约定将范围表示为第一个索引（值）和第一个索引（无效）会更容易混淆。您输入的 0,0,1 意味着第一个索引范围超过 [0,0] 并且您的第二个索引范围超过 [0,1] 包括在内。因此，在某些时候，您将 array[0] 处的数据与其自身进行比较，然后将其添加到输出列表中。使中点和终点互斥意味着范围 [0,1) 和 [1,2) 的输入是明确的。 (在范围内，圆括号表示独占)

Answer 2

在您的命名法中，数组边界是包含在内的：下限是范围的第一个元素，上限是范围的最后一个元素。 mid 元素是左侧子数组的最后一个元素，因此右侧数组以 mid + 1 开头，如您在调用中所见：

        mergeSort(array, lowerIndex, middle);        // sort left array
        mergeSort(array, middle + 1, higherIndex);   // sot right array

但是在 merge 中，您将 mid 分配给正确的范围：索引 q 应该从中间后一个元素开始。（另外，您使用的限制不一致：在第一个循环中，您从 p 或 q 中选择较小的元素，您测试 p<=middle，这与您的命名法一致，后来你使用 p<middle.

这是您的 merge 更正函数：

       var merge = function(array, p, middle, r) {
          console.log(p, q, r);
          var tmp = {};
          var k = p;
          var q = middle + 1;

          while(p <= middle && q <= r){
            if (array[p] < array[q]){
                tmp[k++] = array[p++];
            } else {
                tmp[k++] = array[q++];
            }
          }

          while(p <= middle) tmp[k++] = array[p++];
          while(q <= r) tmp[k++] = array[q++];

          for(var i in tmp) array[i] = tmp[i];
        }

我同意 Pete 的建议，使用 exclusive 上限。在这个命名法中，子数组是 array[lo:mid] 和 array[mid:hi]，因为 mid 和 hi 的初始值是 array.length，不在范围内。

当数组长度为偶数时，在 mergesort 合并函数中应该做什么，特别是在 size=2 的情况下？

What should be done in a mergesort merge function when the array length is even numbered, especially with the case where size=2?

algorithm

sorting

mergesort