What relational properties must a correct compareTo implementation satisfy, and what breaks if you violate them?

## What a correct ordering must guarantee `compareTo` does not just answer "which is first" for one pair — it must define a coherent **total order** over the whole type, so that algorithms can sort and search reliably. The `Comparable` contract states this as three algebraic properties. Let `sgn(n)` denote the sign of an integer (-1, 0, or +1). ### 1. Antisymmetry (sign reversal) > `sgn(x.compareTo(y))` must equal `-sgn(y.compareTo(x))` for all `x`, `y`. If `x` comes before `y`, then `y` must come after `x`. Also: `x.compareTo(y)` may throw an exception **only if** `y.compareTo(x)` would throw too (e.g. on incompatible types). You cannot have `x < y` and also `y < x`. ### 2. Transitivity > if `x.compareTo(y) > 0` **and** `y.compareTo(z) > 0`, then `x.compareTo(z) > 0`. Greater-than chains through. If `x` beats `y` and `y` beats `z`, then `x` must beat `z`. This is the property most often broken by clever-but-wrong logic (e.g. comparators that prefer A over B, B over C, but C over A — a cycle). ### 3. Equality substitutes > if `x.compareTo(y) == 0`, then `sgn(x.compareTo(z)) == sgn(y.compareTo(z))` for all `z`. Objects that are ordering-equal must order identically against every third object — they are interchangeable for comparison purposes. **Reflexivity** — `x.compareTo(x) == 0` — follows from these (set `y = x` in antisymmetry). ## Why these matter: the algorithms assume them Sorting (`Collections.sort`, `Arrays.sort`, `Stream.sorted`, `PriorityQueue`) and searching (`Collections.binarySearch`, `TreeMap`/`TreeSet` navigation) are all built on the assumption that the ordering is a valid total order. If it is not, their results are **undefined**: - **TimSort guard.** Since Java 7, `Arrays.sort`/`Collections.sort` use TimSort, which actively detects gross contract violations and throws: ``` java.lang.IllegalArgumentException: Comparison method violates its general contract! ``` This is a *symptom*, not the bug — it means your `compareTo`/`Comparator` is not transitive/antisymmetric. It is not guaranteed for every violation, only when TimSort happens to notice an inconsistency. - **Wrong order.** A subtler violation may silently produce a list that is not actually sorted. - **Lost keys.** A `TreeMap` built on a broken comparison may store a key yet fail to find it (`get` returns null) because navigation took a wrong branch. ## Common ways people break it - **Non-transitive composite logic.** e.g. comparing by a tolerance band: "equal if within 10" is not transitive (a≈b, b≈c, but a far from c). - **`Integer` subtraction overflow** (`a - b`), which flips the sign for far-apart values, breaking antisymmetry/transitivity. - **Floating-point `NaN`.** `NaN` is unordered: every direct `<`/`>` comparison with it is false, so naive `double` comparison breaks the contract. Use `Double.compare`, which gives `NaN` a defined position. - **Branch-by-branch field comparison that doesn't cover all cases**, leaving some pairs inconsistent. ## The safe recipe Compare field by field in priority order, each with `Integer.compare`/`Double.compare`/the field's own `compareTo`, returning at the first non-zero; or build the ordering with `Comparator.comparing(...).thenComparing(...)`, which is transitive and overflow-safe by construction: ```java Comparator<Person> c = Comparator .comparingInt(Person::age) .thenComparing(Person::lastName) .thenComparing(Person::firstName); ``` Using these building blocks makes it almost impossible to violate the three properties.