Transitivity property of String comparison in java

Question

take a look at this code

   class StringComparator implements Comparator<String> {

     @Override
     public int compare(String a, String b) {
         if (a.length() == b.length()) {
             return b.compareTo(a);
         } else {
             String ab = a + b;
             String ba = b + a;
             return ba.compareTo(ab);
         }
     }
 }

ba.compareTo(ab) works but ab.compareTo(ba) fails. It throws an IllegalArgumentException citing a violation of the comparator contract. I believe its due to the fact that the transitivity property was not satisfied. Can someone please explain how Java uses the transitivity property in case of Strings ? Does this have anything to do with how Timsort works ?

EDIT: Here is the error i get on the Leetcode online judge

Runtime Error Message:
                Line 32: java.lang.IllegalArgumentException: Comparison method violates its general contract!




              Last executed input:
                [7286,155,351,6059,9686,2668,9551,5410,7182,170,3746,3095,8139,2587,2351,2341,2038,3956,6034,4071,9473,281,9306,8746,7954,8937,7855,3938,9737,2455,4344,2986,8968,1072,2442,7191,9106,4236,2768,5214,7541,329,7530,9068,9644,3539,5177,5332,2065,8245,7494,8454,604,4632,1745,301,3412,1569,8637,7840,7752,9536,1023,4841,1286,6489,8459,2725,8021,5026,7058,4540,9892,5344,1205,4363,959,9729,9225,9733,8417,9873,3721,1434,5136,6111,6189,780,4741,2670,2457,5424,1040,3746,1229,8568,3636,1546,2553,575]

Again, i dont get this error when i use ba.compareTo(ab). I

Answer 1

Yes, your compare doesn't seem to respect the transitive property if a and b have different lengths.

This is the Comparator.compare(a,b) contract, see the bold part regarding transitivity:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact. The recommended language is "Note: this comparator imposes orderings that are inconsistent with equals."

Update:

Just to add an interesting side-note, you refer to Tim sort as the sorting algorithm applied by Collections.sort(),etc... , for smaller arrays (size under an hard-coded threshold), a simple merge sort is performed instead. The choice is made at the beginning of the sort method, see openJDK sources for more info.