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

Question

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

这里的mergesort函数通过了测试用例，但它只是被调试的merge函数。

我本以为 0,0,1 是一个无效的参数规范，但是没有，没有其他方法可以传递 length=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) 的输入是明确的。 (在范围内，圆括号表示独占)