What is the 'Comparison method violates its general contract!' exception, what causes it, and how do you fix it?

## The exception ``` java.lang.IllegalArgumentException: Comparison method violates its general contract! ``` It comes from **TimSort** (the merge sort Java uses for object arrays/lists since Java 7). TimSort exploits ordering invariants while merging sorted runs; if your comparator is inconsistent, those invariants break and TimSort detects it mid-sort and bails out with this exception. Java 6's older mergesort often **silently** produced a wrong order instead - so the same buggy comparator may have 'worked' before and started throwing after an upgrade. ### The contract a comparator must obey (a total order) For all a, b, c: 1. **Sign symmetry (antisymmetry):** `sign(compare(a,b)) == -sign(compare(b,a))`. 2. **Transitivity:** if `compare(a,b) > 0` and `compare(b,c) > 0` then `compare(a,c) > 0`. 3. **Transitivity of equality:** if `compare(a,b) == 0` then `sign(compare(a,c)) == sign(compare(b,c))` for every c. Violate any and the order isn't a total order; TimSort may throw. ### Common causes 1. **Subtraction overflow.** `(a, b) -> a.value - b.value` overflows int near `Integer.MAX/MIN_VALUE`, flipping the sign and breaking symmetry/transitivity. Use `Integer.compare(a.value, b.value)`. 2. **Ad-hoc 'priority' logic.** Hand-rolled rules like 'a wins if it has flag X, else b wins if flag Y, else equal' are easy to make non-transitive. Reduce to comparing well-defined keys. 3. **Floating point / NaN.** `Double.compare` is a total order (it orders NaN consistently); raw `<`/`>` on doubles with NaN is **not** (NaN compares false to everything). Always use `Double.compare`. 4. **Mutable sort keys.** If the data being sorted changes (another thread mutates it, or the key depends on a clock/random) during the sort, comparisons become inconsistent across calls. Sort over a stable snapshot. 5. **Inconsistent tie-breakers / mixing equals and compare** in a way that isn't a strict order. ### How to fix / harden - Build comparators from `Comparator.comparing*` + `thenComparing` over **well-defined, immutable keys**; let the JDK's correct key comparisons do the work. - Replace every subtraction with `Integer.compare`/`Long.compare`/`Double.compare`. - Use `Double.compare` (never `<`) for floating keys; decide where NaN/null go (`nullsFirst/Last`). - Never order on mutable or nondeterministic state; snapshot first. - Test the contract: for a representative set, assert sign-symmetry and transitivity, or randomized property tests. ### Escape hatch (last resort, not a fix) Setting `-Djava.util.Arrays.useLegacyMergeSort=true` reverts to the Java 6 mergesort that tolerates a broken comparator by *silently* producing some order. This **hides** the bug rather than fixing it and should only be a temporary mitigation while you repair the comparator. ### Why it matters at scale This bug is data-dependent: it can pass all small tests and surface only on a specific large input in production. Treat the exception as a signal of a real ordering-logic defect, fix the comparator's totality, and add property-based tests so it can't regress.