What does 'Comparison method violates its general contract!' mean?

The Answer

• A comparator must define a total order. Three rules, all of them checkable:
  • antisymmetry — sgn(compare(x, y)) == -sgn(compare(y, x)), for every pair;
  • transitivity — if x > y and y > z, then x > z;
  • substitution — if compare(x, y) == 0, then x and z compare the same way for any z.
• Arrays.sort and List.sort use TimSort, which merges runs. A merge assumes the order is total; when the assumption fails the merge can read past its bounds, so TimSort checks and throws IllegalArgumentException instead.
• The exception is the good outcome. The same broken comparator on a smaller list sorts "successfully" into an order that is simply wrong.
• Two causes account for nearly all of it: return x - y (overflows), and a comparator that never returns 0.
• Optional fourth rule: being consistent with equals — compare(x, y) == 0 exactly when x.equals(y). Not required, but TreeMap and TreeSet behave strangely without it.

Understand It

The contract is about pairs, not about sorting

compare looks like it answers "which is bigger", but what it is really doing is defining an ordering over the whole set, one pair at a time. Sorting algorithms then trust that ordering — they skip comparisons they can deduce. If a < b and b < c, a merge sort will never compare a with c; it already knows. Break transitivity and it acts on knowledge it does not have.

So the rules are not bureaucracy. They are precisely the facts a sorting algorithm is allowed to assume without checking.

Cause one: x - y

The oldest trick in the book, and it is wrong:

Comparator<Integer> bySubtraction = (x, y) -> x - y;

int big = Integer.MAX_VALUE, small = -2;
System.out.println("x - y gives     : " + bySubtraction.compare(big, small));
System.out.println("so it claims    : " + big + " < " + small + "? "
    + (bySubtraction.compare(big, small) < 0));
System.out.println("Integer.compare : " + Integer.compare(big, small));

x - y gives     : -2147483647
so it claims    : 2147483647 < -2? true
Integer.compare : 1

MAX_VALUE - (-2) overflows and wraps negative, so the comparator reports that the largest int is smaller than −2. It is correct for every pair whose difference fits in an int, which is every pair in your unit test and most pairs in production. Use Integer.compare(x, y) — it is a three-way branch with no arithmetic, and it cannot overflow.

Cause two: never returning 0

This one usually comes from wanting a stable tiebreak and reaching for the wrong tool:

Comparator<int[]> never0 = (x, y) -> x[0] < y[0] ? -1 : 1;

int[] p = {5}, q = {5};
System.out.println("compare(p, q) = " + never0.compare(p, q));
System.out.println("compare(q, p) = " + never0.compare(q, p));
System.out.println("antisymmetry needs these to be opposite signs.");

compare(p, q) = 1
compare(q, p) = 1
antisymmetry needs these to be opposite signs.

Both directions say "greater". For two equal values the comparator claims each is bigger than the other, which is not an ordering at all — and no amount of sorting can repair it.

Why it only throws sometimes

Here is the part that makes this a production bug rather than a test failure. The same broken comparator, the same data distribution, only the size changing:

Comparator<int[]> never0 = (x, y) -> x[0] < y[0] ? -1 : 1;

for (int n : new int[] {8, 16, 31, 32, 40, 64}) {
    List<int[]> list = new ArrayList<>();
    Random r = new Random(7);
    for (int i = 0; i < n; i++) list.add(new int[] { r.nextInt(4) });
    try {
        list.sort(never0);
        System.out.println("n=" + n + "  sorted, no complaint");
    } catch (IllegalArgumentException e) {
        System.out.println("n=" + n + "  THREW: " + e.getMessage());
    }
}

n=8  sorted, no complaint
n=16  sorted, no complaint
n=31  sorted, no complaint
n=32  sorted, no complaint
n=40  sorted, no complaint
n=64  THREW: Comparison method violates its general contract!

Below 32 elements TimSort does not merge at all — it uses a binary insertion sort, which never relies on transitivity, so there is nothing to detect. Above that it merges, and whether the broken pair happens to land where a merge notices depends on the data. Every one of those "sorted, no complaint" lines produced an order the comparator's own rules do not justify. The list that threw is the only one that told you.

This is why the exception reads like a JDK bug report and is not one. The JDK is reporting that it was lied to.

The optional rule: consistency with equals

compare(x, y) == 0 and x.equals(y) are allowed to disagree, and the JDK ships a comparator that does exactly that. But sorted collections define duplicates by the comparator, not by equals:

TreeSet<String> sorted = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
sorted.add("Java");
sorted.add("java");
sorted.add("JAVA");

Set<String> hashed = new HashSet<>(List.of("Java", "java", "JAVA"));

System.out.println("TreeSet, case-insensitive : " + sorted + "  size=" + sorted.size());
System.out.println("HashSet, same strings     : size=" + hashed.size());

TreeSet, case-insensitive : [Java]  size=1
HashSet, same strings     : size=3

Two Sets, the same three strings, and they disagree about how many distinct elements there are. Neither is broken — TreeSet asks the comparator, HashSet asks equals. The documentation calls a TreeSet like this "well defined but fails to obey the general contract of Set", which is unusually frank, and it is why SortedSet documents the recommendation rather than enforcing it.

Reference

Write it this way and the contract holds by construction:

// WRONG — overflows
Comparator<Integer> bad = (x, y) -> x - y;

// RIGHT — no arithmetic
Comparator<Integer> good = (x, y) -> Integer.compare(x, y);
Comparator<Item> byCount = Comparator.comparingInt(Item::count);

// Chained tiebreaks — each key compared properly, 0 only when all are equal
Comparator<Item> ordering = Comparator
        .comparing(Item::name)
        .thenComparingInt(Item::count)
        .thenComparing(Item::id);

// Nulls, declared rather than crashed into
Comparator<Item> safe = Comparator.nullsFirst(Comparator.comparing(Item::name));

// Reverse — not by swapping the arguments, which breaks on MIN_VALUE
Comparator<Item> newestFirst = Comparator.comparing(Item::created).reversed();

The factory methods exist precisely because hand-written comparators get the contract wrong. comparingInt cannot overflow, thenComparing only runs when the previous key returned 0, and reversed() negates the result of a branch rather than negating a number that may be Integer.MIN_VALUE.

Checking your own comparator, which is worth doing for anything non-trivial:

// Every pair, both directions. O(n^2), so run it in a test, not in production.
for (T x : sample)
    for (T y : sample)
        assert Integer.signum(cmp.compare(x, y)) == -Integer.signum(cmp.compare(y, x));

// Transitivity, on triples
for (T x : sample) for (T y : sample) for (T z : sample)
    if (cmp.compare(x, y) > 0 && cmp.compare(y, z) > 0)
        assert cmp.compare(x, z) > 0;

Scenarios

Sorting search results by relevance. A comparator built from a float score that is occasionally NaN. Every comparison involving NaN returns false, so the comparator reports "not less, not greater, not equal" — it silently breaks antisymmetry. Double.compare handles NaN with a total order; < and > on doubles do not.

Priority by "importance", defined by a mutable field. The comparator is fine; the data moves underneath it. If a field changes while the object sits in a PriorityQueue or TreeMap, the structure's invariants are already broken and no exception will tell you. Sort keys must be effectively immutable for as long as the collection holds them.

A comparator that "works" after someone added a tiebreak. The team hits the exception, adds .thenComparing(Item::id) and it goes away. Sometimes that is the correct fix — the missing tiebreak was the bug. Sometimes it only pushes the broken pair somewhere TimSort stops looking. Check the primary comparison for overflow before accepting that the tiebreak fixed anything.

You genuinely want a partial order. Some domains have incomparable pairs — versions across branches, permissions in a lattice. A Comparator cannot express that, and forcing it is where non-transitive comparators come from. Use an explicit graph or a topological sort instead.

Interviewer's Next Move

1. "Why does x - y pass code review so often?" Because it is correct for every pair whose difference fits in an int, which is all of them until the data includes values near the extremes. Ages, counts and sizes never break it; timestamps, hashes and user-supplied ints do. The failure needs both a large positive and a large negative operand.

2. "Is the exception guaranteed?" No. TimSort throws when a merge detects the inconsistency, which depends on size and data — under 32 elements it never merges, so it cannot detect anything. A broken comparator that never throws is not a working comparator; it is one producing wrong orders quietly.

3. "Must compare be consistent with equals?" Not required, and String.CASE_INSENSITIVE_ORDER deliberately is not. But a TreeSet using it treats "Java" and "java" as one element, so it violates Set's own contract as documented. Required for correctness in sorted collections; optional elsewhere.

4. "How does Comparator.reversed() differ from swapping the arguments?" reversed() calls the original and negates its sign decision. (a, b) -> -cmp.compare(a, b) negates the returned int, and if the comparator ever returns Integer.MIN_VALUE — which x - y can — negating it gives Integer.MIN_VALUE again, so "reversed" compares the same direction as the original.

5. "Where else does the same contract show up?" Comparable.compareTo, with the same three rules, plus a recommendation to be consistent with equals. equals and hashCode carry a parallel contract, and breaking that one loses entries in a HashMap rather than throwing. Contracts are how the JDK states what it will assume without checking.

Check Yourself

Why is (x, y) -> x[0] < y[0] ? -1 : 1 broken even though it never returns a wrong answer for unequal values? Because for equal values it returns 1 in both directions, so sgn(compare(x, y)) and -sgn(compare(y, x)) disagree. It never reports equality, so it is not an ordering.

A sort of 20 elements works and the same code throws on 2,000. What changed? Nothing about the comparator. Below 32 elements TimSort uses binary insertion sort and never merges, so it cannot notice. The 20-element sort was also producing an unjustified order — it just did so quietly.

compare returns 0 but equals returns false. Where does that bite? In TreeMap and TreeSet, which define duplicates by the comparator. The second element is treated as already present and silently dropped. A HashMap of the same objects keeps both, so the two collections disagree about the data.