Create a method to check if sorting algorithm is stable

First, a stable sort is one in which elements that test as equal remain in their same relative positions within a list after the sort has completed.

Here is one approach for demonstrating that the sort appeared to be stable or unstable.

1. Create a list of objects which are randomize based on their sorting criteria.
2. Maintaining the same order, add a sequential id to each object. This id should not be part of the sorting criteria.
3. Now sort them in ascending order.

Now you can run through the sorted list and checking only equal elements, see if the ids are in ascending order. If they are, the sort behaved like a stable sort. If they are not, it behaved like an unstable sort.

Note that testing will not guarantee stability because continued stable sorts will not guarantee future stable sorts. Past outcomes don't influence future outcomes.

But a single unstable result proves that the sort is unstable.

Note: Adding the id above is simply one method. Tracking indices of equal elements could be another. The idea is to show that the equal elements remained in their relative positions to each other.

To test sort stability:

• Create 2 (or more) objects that are different but compare equal.
• Add them to a list.
• Add them to another list, but in opposite order.
• (Optional) Add other objects, before/after/between the "equal" objects.
• Sort both lists.

If the order of the "equal" objects stayed in insertion-order, then it is highly probable that the sort is stable. It is not a 100% guarantee, but sorting multiple lists of varying length increases confidence level of the test.

Example

class StringNum implements Comparable<StringNum> {
    private final String s;
    private final int n;
    public StringNum(String s, int n) {
        this.s = s;
        this.n = n;
    }
    @Override
    public int compareTo(StringNum that) {
        return this.s.compareTo(that.s); // Only order by string, not by number
    }
    @Override
    public String toString() {
        return this.s + ":" + this.n;
    }
}

StringNum a1 = new StringNum("A", 1);
StringNum b1 = new StringNum("B", 1);
StringNum b2 = new StringNum("B", 2);
StringNum c1 = new StringNum("C", 1);
StringNum c2 = new StringNum("C", 2);
StringNum c3 = new StringNum("C", 3);
StringNum d1 = new StringNum("D", 1);
StringNum d2 = new StringNum("D", 2);
StringNum d3 = new StringNum("D", 3);
StringNum d4 = new StringNum("D", 4);
StringNum e1 = new StringNum("E", 1);
StringNum e2 = new StringNum("E", 2);
StringNum e3 = new StringNum("E", 3);
StringNum e4 = new StringNum("E", 4);
StringNum e5 = new StringNum("E", 5);
List<StringNum> list1 = new ArrayList<>(Arrays.asList(a1, b1, c1, d1, e1, b2, c2, d2, e2, c3, d3, e3, d4, e4, e5));
List<StringNum> list2 = new ArrayList<>(Arrays.asList(e5, e4, e3, e2, e1, d4, d3, d2, d1, c3, c2, c1, b2, b1, a1));
Collections.sort(list1);
Collections.sort(list2);
System.out.println(list1);
System.out.println(list2);

Output

[A:1, B:1, B:2, C:1, C:2, C:3, D:1, D:2, D:3, D:4, E:1, E:2, E:3, E:4, E:5]
[A:1, B:2, B:1, C:3, C:2, C:1, D:4, D:3, D:2, D:1, E:5, E:4, E:3, E:2, E:1]

Since both lists are correct sorted by letter, first list keeps numbers in inserted ascending order, and second list keeps numbers in inserted descending order, we can conclude that Collections.sort() appears to be stable.