Comparison method violates its general contract

Key points

• A comparator must be transitive, antisymmetric and consistent. Break any of them and sorting is undefined - it may work, may order wrongly, or may throw.
• The classic break is a - b on ints. It overflows for large or negative values, so the sign flips and transitivity fails. Use Integer.compare.
• TimSort - the algorithm behind Arrays.sort for objects - detects some violations and throws IllegalArgumentException: Comparison method violates its general contract.
• It only detects them on lists large enough to trigger the merge path, typically above 32 elements. So the bug passes every small unit test and appears in production.
• Floating point breaks it too: a comparator returning 0 for NaN comparisons is inconsistent, because NaN is not equal to anything.
• A comparator inconsistent with equals is legal but breaks TreeMap and TreeSet, which use compareTo rather than equals to decide membership.

Example

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

public class ComparatorContract {

    record Item(String name, int weight) { }

    public static void main(String[] args) {
        // BROKEN: subtraction overflows and the sign flips.
        Comparator<Item> broken = (x, y) -> x.weight() - y.weight();

        Item big = new Item("big", Integer.MAX_VALUE);
        Item small = new Item("small", -1);
        System.out.println("MAX_VALUE - (-1) overflows to: " + (Integer.MAX_VALUE - -1));
        System.out.println("broken says big < small     : " + (broken.compare(big, small) < 0));

        Comparator<Item> correct = Comparator.comparingInt(Item::weight);
        System.out.println("correct says big > small    : " + (correct.compare(big, small) > 0));

        // Small list: the violation is not detected.
        List<Item> smallList = new ArrayList<>();
        smallList.add(big);
        smallList.add(small);
        smallList.sort(broken);
        System.out.println();
        System.out.println("2 elements sorted without complaint: " + smallList.size());

        // Large list: TimSort takes the merge path and detects it.
        List<Item> large = new ArrayList<>();
        for (int i = 0; i < 40; i++) {
            large.add(new Item("i" + i, i % 2 == 0 ? Integer.MAX_VALUE - i : -i));
        }
        try {
            large.sort(broken);
            System.out.println("40 elements: sorted (violation not hit this time)");
        } catch (IllegalArgumentException e) {
            System.out.println("40 elements: " + e.getMessage());
        }

        // Inconsistent with equals: TreeSet uses compareTo for MEMBERSHIP.
        Comparator<String> byLength = Comparator.comparingInt(String::length);
        TreeSet<String> set = new TreeSet<>(byLength);
        set.add("cat");
        set.add("dog");           // same length -> compare returns 0 -> DUPLICATE
        System.out.println();
        System.out.println("TreeSet(byLength) after adding cat, dog: " + set);
        System.out.println("  size = " + set.size() + "  <- dog was treated as equal to cat");

        // Fix: make the comparator a total order.
        TreeSet<String> fixed = new TreeSet<>(byLength.thenComparing(Comparator.naturalOrder()));
        fixed.add("cat");
        fixed.add("dog");
        System.out.println("with a tie-breaker                    : " + fixed);
    }
}

Never subtract to compare, and always add a tie-breaker - a broken comparator passes small tests and throws in production.