Writing a proper implementation of compareTo

private static class CharacterIndex implements Comparable<CharacterIndex> {
    private final char c;
    private final int index;

    public CharacterIndex(char c, int index) {
        this.c = c;
        this.index = index;
    }
}

Now I want to override the compareTo method for this class such that if I have the following List of CharacterIndex's objects [('y', 1), ('x', 2), ('b', 3), ('a', 3)] then after sorting, the objects should be like [('b', 3), ('a', 3), ('x', 2), ('y', 1)].

Sorting Strategy:

Objects for which the index is different can be shuffled (and should be in sorted order based only on the character's value). Objects that have same index should maintain their relative order after sorting.

One more example:

For [('y', 1), ('w', 2), ('x', 3)] the sorted list should be [(w, 2), (x, 3), (y, 1)] and not [(x, 3), (w, 2), (y, 1)].

My attempt:

@Override
public int compareTo(CharacterIndex ci) {
    if (this.index == ci.index)
        return -1; // don't swap if the index is same
    return Character.compare(this.c, ci.c);
}

But this approach gives me an exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:141)

I saw this. But I couldn't clearly understand why am I getting this exception.

Is there a better way to sort the List<CharacterIndex> with the above given strategy?

Solution

Putting @RealSkeptic's comments into answer:

The java-docs of `Comparable` says that:

This interface imposes a total ordering on the objects of each class that implements it.

Total-ordering should follow the following properties:

Reflexivity
Antisymmetry
Transitivity
Comparability

To see more on what totally ordered sets are see this link.

My sorting strategy is not transitive.

Suppose my initial list is [(d,2), (y,1), (b,1)]

(y,1) < (b,1) as for same index, I don't want to shuffle the order.
(b,1) < (d,2) as for different index, I can shuffle order and then I need to compare the character only.

By transitivity, (y,1) < (d, 2). Which is not true.

So this is not a totally ordered comparison. And hence it breaks the rule provided by Comparable interface.

So we can't have a correct implementation of compareTo (which abide by the contract of Comparable interface) for this sorting strategy.

What you learned?

Your sorting strategy should always define total ordering on the objects of class that implements Comparable