Proving mergesort is stable

Viewed 1515

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
3 Answers
Related