"Comparison method violates general contract " while sorting multi dimensional array

Question

I am sorting a 2-d array using custom comparator and getting the following error in some cases :

java.lang.IllegalArgumentException: Comparison method violates its general contract! at line 781, java.base/java.util.TimSort.mergeLo at line 518, java.base/java.util.TimSort.mergeAt at line 448, java.base/java.util.TimSort.mergeCollapse at line 245, java.base/java.util.TimSort.sort at line 1442, java.base/java.util.Arrays.sort

Below is the code that is throwing this error :

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new SortComparator());
    }
}

class SortComparator implements Comparator<int[]> {
    public int compare(int []a, int []b) {
        if(a[0] < b[0]) {
            return -1;
        } else if(a[0] > b[0]) {
            return 1;
        } else {
            if(a[1] < b[1]) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}

Although when I am using the below implementation of SortComparator class everything works fine :

class SortComparator implements Comparator<int[]> {
    public int compare(int []a, int []b) {
        if(a[0] < b[0]) {
            return -1;
        } else if(a[0] > b[0]) {
            return 1;
        } else {
            if(a[1] < b[1]) {
                return -1;
            } else if(a[1]> b[1]) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}

Can I know because of what reason first implementation of SortComparator is throwing error ?

Stephen C Stephen C · Accepted Answer · 2020-10-11T06:05:40

The problem is that your first SortComparator implementation can never return 0.

Therefore SortComparator.compare(a, a) cannot ever return 0 as it is required to do by "the general contract" for Comparator implementations.

In fact, SortComparator.compare(a, a) will return 1.

The actual contract is in the javadoc. What it says is:

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 only way that sgn(compare(x, y)) == -sgn(compare(y, x)) can be true when x and y are the same object is if -sgn(compare(x, x)) is zero for all x.

^{1 - Nitpick: I think they should have used the word "denotes" rather than "designates" here.}

"Comparison method violates general contract " while sorting multi dimensional array

1 Answers