这个 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];

也就是说，如果数组左侧的元素与右侧的元素相等，则选择右侧的一个。这样做会颠倒这些元素的原始顺序。

这个 MergeSort 实现稳定吗？

Is this MergeSort implementation stable?

algorithm

sorting

mergesort