How do you prove or illustrate that fast merge sort is an unstable algorithm?

Question

A problem puzzled me when I read problem 2.2.10 of chapter 2 of Algorithms, 4th Edition. The book says that the results of the fast merge algorithm are unstable and I cannot find evidence of that.Help me, thanks!

public static void sort(Comparable[] a, int lo, int hi){
    if hi <= lo {
    return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, lo, mid);
    sort(a, mid+1, hi);
    merge(a, lo, mid, hi);
}

// Why is the result of this sort not stable
private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 

   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];

   int i = lo, j = hi; 
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
}

I can't find the results to be unstable, how could I get to that?

Answer 1

To prove the unstability of the algorithm, a single counterexample is sufficient: lets consider the steps taken to sort an array of 4 elements A B C D that compare equal for the less predicate.

• sort(a, 0, 3) recurses on 2 subarrays:
• sort(a, 0, 1) which recurses again
• sort(a, 0, 0) which returns immediately
• sort(a, 1, 1) which returns immediately
• merge(a, 0, 0, 1) does not change the order of A B
• sort(a, 2, 3) which recurses on
• sort(a, 2, 2) which returns immediately
• sort(a, 3, 3) which returns immediately
• merge(a, 2, 2, 3) does not change the order of C D
• merge(a, 0, 1, 3) copies the items A B C D into t in the order A B D C, then all comparisons in the merge loop evaluate to false, hence the elements copied back into a are in the same order, copied from t[i++]: A B D C, proving the instability of the sorting algorithm, ie: the relative order of elements that compare equal is not preserved.