Proving mergesort is stable

Question

I have written a mergesort algorithm. When I run the following test:

public static void main(String[] args){
    Integer[] arr = {3,7,9,11,0,-5,2,5,8,8,1};
    List<Integer> list = new ArrayList<>();
    list.addAll(Arrays.asList(arr)); // asList() returns fixed size list, so can't pass to mergesort()
    List<Integer> result = mergesort(list);
    System.out.println(result);
  }

I get [-5, 0, 1, 2, 3, 5, 7, 8, 8, 9, 11], which is correct. However, I know that mergesort is a stable sort, so how can I write a test that can prove that the two 8's are in the order they originally were?

EDIT: Since I used the Integer class, rather than primitive ints, I figured I could just get the hashCode() since Integer extends the base Object class.

However, when I tried

Integer[] arr = {3,7,9,11,0,-5,2,5,8,8,1};
System.out.println(arr[8].hashCode());
System.out.println(arr[9].hashCode());

I only get:

8
8

You can't, with integers. You would have to sort objects with integer attributes and another attribute that was unique. — user207421, Jul 12 '17 at 02:12
Its more labor intensive but create variables like Integer eightA = new Integer(8) etc. Then you can compare them post sort with == since that compares references, ie, arr[8] == eightA, arr[9] == eightB etc. — terpinmd, Jul 12 '17 at 02:18
The `hashCode()` of an `Integer` is its own value, so you can't use it to distinguish duplicates. You need `==`, or `System.identityHashCode()`. — user207421, Jul 12 '17 at 02:19

Tavo · Accepted Answer · 2017-07-12T02:23:47.553

The best way I can think of is if you wrap the numbers in their wrapper Integer class. If you do the following:

Integer eight = new Integer(8);
Integer anotherEight = new Integer(8);

a == b; //Returns false
a.equals(b); //Returns true

Else, as suggested in the comments, you can add an extra field to your class for comparison.

EDIT: To answer your edit, the Integer.hashcode() documentation states that the hascode is

equal to the primitive int value represented by this Integer object.

score 0 · Answer 2 · answered Jul 12 '17 at 02:24

I think in using a simple Key-Value structure, like some of this or some of that

Using this (to be short):

public class Tuple<X, Y> { 
  public final X x; 
  public final Y y; 
  public Tuple(X x, Y y) { 
    this.x = x; 
    this.y = y; 
  } 
}

you could do:

  public static void main(String[] args)
  {
    Integer[] arr = {new Tuple(3,0),new Tuple(7,1),new Tuple(9,2) ,new Tuple(11,3), new Tuple(0,4), new Tuple(-5,5), new Tuple(2,6), new Tuple(5,7), new Tuple(8,8), new Tuple(8,9), new Tuple(1,10)};
    List<Tuple<Integer,Integer>> list = new ArrayList<>();
    list.addAll(Arrays.asList(arr)); // asList() returns fixed size list, so can't pass to mergesort()
    List<Integer> result = mergesort(list);
    System.out.println(result);
  }

And in the code of the merge sort, only merge for the first item, and let the second be the same, you should see the (8,8) first and then the (8,9)

score 0 · Answer 3 · answered Jul 12 '17 at 08:51

Proof of stability would involve analyzing the merge sort algorithm, not creating test cases where stability tests did not fail. It might be simpler to analyze bottom up merge sort first. First an array of n elements is treated as an array of n runs of length 1, and then those runs are repeatedly merged until a single sorted run is produced. In a k-way merge sort, if the current elements from the k runs are equal, the element from the left most run is moved to the output array, preserving stability.

For top down merge sort, which is normally 2 way, the same rule applies, when equal elements are encountered, the element from the left run is moved, preserving stability.

Proving mergesort is stable

3 Answers3