Mergesort：マージ操作の最後のステップは何ですか？

Question

次のmergeortはデータ構造とアルゴリズム解析（Weiss）です。私が思っているのは、マージステップの最後のforループです。私はtmpArrayをarrayにコピーしなければならないと理解していますが、私たちはrightendからなぜそれを行うのか分かりません。iは0からtmpArray.sizeになります。誰か説明してもらえますか？

私は rightPosの値、部分配列が始まるスポットは、破壊的 rightPos++の使用を注意してください（内部ループによって変更されたため。したがって、順序で物事をこの方法を行うための主な理由があると思い

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で開始し、前方にカウントするために、それは間違ったインデックスにそれを書くことになりました。

言った、私はしないでくださいこのようにする理由を見てください。新しい変数を宣言し、入力を破棄する代わりにそれらの値を変更してe元の値を回復するための体操。

希望すると便利です。