algorithm - Mergesort:合并操作的最后一步是怎么回事？

Question

以下合并排序来自数据结构和算法分析 (Weiss)。我想知道的是合并步骤中的最后一个 for 循环。我知道我们必须将 tmpArray 复制回 array，但我不明白为什么我们从 rightend 开始，为什么我们不这样做没有 i 从 0 到 tmpArray.size。有人可以解释一下吗？

public static void mergeSort( Comparable [ ] a )
{
  Comparable [ ] tmpArray = new Comparable[ a.length ];
  mergesort( a, tmpArray, 0, a.length - 1 );
}

public static void mergesort( Comparable [ ] a, Comparable [ ] tmpArray,
int left, int right )
{
  if( left < right ) {
    int center = ( left + right ) / 2;
    mergesort( a, tmpArray, left, center );
    mergesort( a, tmpArray, center + 1, right );
    merge( a, tmpArray, left, center + 1, right );
  }
}

public static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
int leftPos, int rightPos, int rightEnd )
{

  int leftEnd = rightPos - 1;
  int tmpPos = leftPos;
  int numElements = rightEnd - leftPos + 1;

  while( leftPos <= leftEnd && rightPos <= rightEnd )
    if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
      tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    else
      tmpArray[ tmpPos++ ] = a[ rightPos++ ];

  while( leftPos <= leftEnd ) // Copy rest of first half
    tmpArray[ tmpPos++ ] = a[ leftPos++ ];

  while( rightPos <= rightEnd ) // Copy rest of right half
    tmpArray[ tmpPos++ ] = a[ rightPos++ ];

  for( int i = 0; i < numElements; i++, rightEnd-- )
    a[ rightEnd ] = tmpArray[ rightEnd ]; // Copy tmpArray back
}

Answer 1

我认为这样做的主要原因是 rightPos 的值，子数组开始的地方，已经被内部循环破坏性地修改了(注意 的使用rightPos++。因此，为了正确写回值，最后一个循环倒计时到 rightPos 最初所在的位置。它是否只是从 rightPos 开始往前数，它会写入错误的索引。

也就是说，我认为没有任何理由这样做。只声明新变量并修改这些值会更容易，而不是破坏输入并进行额外的体操以恢复原始值。

希望这对您有所帮助!