這個MergeSort實現是否穩定？

Question

我正在學習我的算法考試。有人可以解釋爲什麼這不穩定，問題在哪裏變得不穩定？我怎樣才能使它穩定？

感謝

//The numbers to be sorted are given in array A[1..n] 
//We use an additional array B[1..n] as temporary storage space 
MergeSort(A, left, right) { 
    if (left < right) { 
     mid = floor((left + right)/2);  // find the middle 
     MergeSort(A, left, mid);    // sort the left subarray recursively 
     MergeSort(A, mid+1, right);   // sort the right subarray recursively 
     Merge(A,left,mid,right);    // merge the two sorted subarrays 
    } 
} 

Merge(A, left, mid, right) { 
    // left subarray: A[left..mid], right subarray: A[mid+1 .. right] 
    m = left; // index for the temporary array 
    i = left; 
    j = mid+1; 
    while (i <= mid && j <= right) {  // copy the smaller element to the output 
     if (A[i] >= A[j]) { 
      B[m] = A[j]; 
      j++; 
     } else { 
      B[m] = A[i]; 
      i++; 
     } 
     m++; 
    } 
    while (i <= mid) {     // copy the remaining part in the left array 
     B[m] = A[i]; 
     m++; 
     i++; 
    } 
    while (j <= right) {     // copy the remaining part in the right array 
     B[m] = A[j]; 
     m++; 
     j++; 
    } 
    for (m = left; m <= right; m++)  // copy the merged form back to A 
     A[m] = B[m]; 
} 

Answer 1

您的問題是在這個領域：

i = left; 
j = mid+1; 
while (i <= mid && j <= right) { // copy the smaller element to the output 
    if (A[i] >= A[j]) { 
     B[m] = A[j]; 

，說，如果從陣列的左側部分的元素等於從右側的元素，選擇一個從右邊。這樣做會顛倒這些元素的原始排序。