Search code examples
algorithmsortingmergesort

Is this MergeSort implementation stable?


I am studying for my algorithms exam. Someone can explain me why this is not stable and where is the problem that is not becoming stable? And how can I make it stable?

Thanks

//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];
}

Solution

  • Your problem is in this segment:

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

    That says that if an element from the left part of the array is equal to an element from the right, choose the one from the right. Doing so will reverse the original ordering of those elements.