java - MergeSort算法中的Merge方法

Question

我见过很多合并排序的实现。这是 Robert Lafore 在 Java 中的数据结构和算法(第 2 版)中的版本:

private void recMergeSort(long[] workSpace, int lowerBound,int upperBound)
  {
  if(lowerBound == upperBound)            // if range is 1,
     return;                              // no use sorting
  else
     {                                    // find midpoint
     int mid = (lowerBound+upperBound) / 2;
                                          // sort low half
     recMergeSort(workSpace, lowerBound, mid);
                                          // sort high half
     recMergeSort(workSpace, mid+1, upperBound);
                                          // merge them
     merge(workSpace, lowerBound, mid+1, upperBound);
     }  // end else
  }  // end recMergeSort()


  private void merge(long[] workSpace, int lowPtr,
                           int highPtr, int upperBound)
      {
      int j = 0;                             // workspace index
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1;       // # of items

      while(lowPtr <= mid && highPtr <= upperBound)
         if( theArray[lowPtr] < theArray[highPtr] )
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()

关于 merge 方法的一件有趣的事情是几乎所有的实现都没有将 mid 参数传递给 merge 方法。 mid 在合并中计算。这很奇怪，因为从调用方法中将 highPtr 分配给了 mid + 1。

为什么作者没有像merge(workSpace, lowerBound,mid, mid+1, upperBound);那样通过mid进行合并？如果我们这样写，我们可以很容易地看到 [lowerBound,mid] 是较低的范围，[mid+1,upperBound] 是较高的范围。 我想一定是有原因的，否则我无法理解为什么一个超过半个世纪的算法的所有实现都在这么小的细节上重合。

Answer 1

基本上我们讨论的是相邻的 [a..b-1] 和 [b..n] 的两个区间(包括边界)，以及你问为什么它显示为 (a, b, n) 而不是 (a, b-1, b, n)？

你自己也说过:就是“这么小的细节”。

它不影响正确性，并且不重新计算 b-1 所获得的任何性能可能会被将其作为附加参数传递的成本所抵消。以一种或另一种方式进行分析是否值得付出努力？不会。它对算法的渐近行为没有影响，任何性能差异都可以忽略不计；不值得为这样的小事大惊小怪。

顺便说一下，值得注意的是，上面计算两个数的平均值的方法现在被认为是错误的(参见:Google Research blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken)。 Josh Bloch 建议:

int mid = (low + high) >>> 1;

---

回到最初的问题，一般来说，如果一个参数可以从另一个参数推导出来，那么通常最好省略它们；它简化了调用，并且由于域明显更小，也简化了分析。

一个函数有 10 个参数，其中 5 个是可导的，比只需要 5 个参数的函数更难分析。当然，如果可导参数很昂贵和/或计算起来很重要，并且您已经在调用函数之前计算它们的值，然后您可以考虑传递它们。

事实上，在合并排序示例中，(a, n) 就足够了，因为 b 可以从两者派生。然而，该计算并非微不足道(Bloch 提到的错误在 2 年内逃脱了检测)，因此决定简单地传递它。

相比之下，

b-1 过于琐碎，最好省略。