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

A sorting algorithm that keeps "equal" elements in the same order is considered stable. Thus unstable means: you have multiple equal elements, and when you sort the overall list/array, the output of that sorting has those equal elements (potentially) showing up in a different order.

Assume for example you have a Person class, and equality is implemented to only look on the last name, and to ignore the first name.

Now, assume you have two Person objects, representing "John Doe" and "Jane Doe". They are in your unsorted list in that order.

Stable would mean: you always end up with "John Doe" appearing before "Jane Doe". With an unstable sort, you do not have that guarantee.

In other words: you need to create a class that has at least two attributes. Then you need to define compareTo() to only rely on one of the two properties.

Then you create some example list of objects of that class, and then you experiment long enough until you find an example where the sorted list shows that equal objects changed order.

In other words: create a list (p1, p2, p3, p4, ...), sort that, and then look out for a result that maybe says ... p4, p3 ... although p4 and p3 are considered "equal".

Finally: this would actually be a very nice use case for using some property based testing framework, such as QuickCheck. Using such a framework, you would need to:

• create a "generator" that can create "random" objects of some class you later sort on (where you skew the generator to ensure you get a bunch of "equal" objects out of it)
• then have the framework test the underlying "assertion" that the order of "equal" objects before and after sorting must not change.

And then have the framework do its magic ...

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.

To prove a sort algorithm is unstable only requires finding one failure. Proving a sort algorithm is stable would be more involved. One way to check for failure is to use an array of integers and split the integers into two parts, the upper 8 bits as a pseudo random value, the lower 24 bits equal to the index of the integer (0 to count-1). Then run the sort, using only the upper 8 bits for the compare, for example in C:

    if((b[j]&0xff000000) < (b[i]&0xff000000)) ...

After the sort is completed, check that the array is in order using all 32 bits.

Using this method, I was able to confirm that this variation of merge sort is unstable.

Apparently the reason this is called "fast" merge sort, is that there is no check for the end of a run when doing the merge. The left run is copied into aux[] in forward order from lo to mid, while the right run is copied into aux[] in reverse order from hi to mid+1. The merge then starts at both ends (lo and hi) and works towards the middle (mid and mid+1), the left run using i forwards from lo to mid, the right run backwards using j from hi to mid+1. Since there is no check for reaching the end of a run, i may be incremented above mid (potential stability issue), or j may be decremented below mid+1 (not a stability issue). Stability is broken in the case where i is incremented above mid, and aux[mid+1] == aux[mid+2], the two highest elements from the original right run. In this case the elements are copied in reverse order.

Although the book called it fast merge sort, it would be faster to avoid copying the data in aux, and instead changing the direction of merge based on the level of recursion. For top down, this can be done with a one type copy and swapping array references in the recursive calls, such as this wiki example:

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

The initial copy can be avoided using a pair of mutually recursive functions, one that ends up with the result in a[], the other that ends up with the result in b[].

Slightly faster is a bottom up merge sort, since it skips all of the recursive splitting and storing of indexes on the stack. In this case, the direction of merge is based on the merge pass. To keep the number of passes even, a check can be made in advance for an odd pass count, and pairs of elements swapped in place before starting the first bottom up merge sort pass.