> ## Content Index
> Fetch the complete content index at: https://www.ggorantala.dev/llms.txt
> Use this file to discover other available public pages before exploring further.

# Comparison Method Violates Its General Contract in Java
- URL: https://www.ggorantala.dev/java-illegalargumentexception-comparison-method-violates-general-contract/
- Published: 2026-08-23T09:19:00.000Z
- Updated: 2026-08-31T09:23:03.000Z
- Description: IllegalArgumentException: Comparison method violates its general contract! comes from TimSort, not your code. Here is why it fires, and how to fix the comparator.
- Author: Gopi Gorantala
- Tags: Java, java-errors, illegalargumentexception, timsort, comparator, java-collections, core-java, jvm

## 1\. The Error

```Log
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
	at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
	at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
	at java.base/java.util.TimSort.sort(TimSort.java:245)
	at java.base/java.util.Arrays.sort(Arrays.java:1308)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at BadComparator.main(BadComparator.java:25)
```

The message string has not changed since TimSort landed in Java 7\. What changes is the frame list:

- **Java 8** has no module prefix and slightly different line numbers: `at java.util.TimSort.mergeLo(TimSort.java:777)`, `mergeAt(TimSort.java:514)`, `mergeCollapse(TimSort.java:441)`.
- **Java 11 / 17 / 21 / 25** all show `java.base/java.util.TimSort.mergeLo(TimSort.java:781)`. `TimSort.java` is byte-for-byte identical between JDK 21 and JDK 25 — the only frames that move are the `Arrays.sort` and `ArrayList.sort` line numbers.
- If you sort by **natural ordering** (a broken `compareTo`) instead of a `Comparator`, the top frames come from a different class:

```Log
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.ComparableTimSort.mergeLo(ComparableTimSort.java:748)
	at java.base/java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:485)
	at java.base/java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:413)
	at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
	at java.base/java.util.Arrays.sort(Arrays.java:1042)
```

`Arrays.sort(T[], Comparator)` declares this in its Javadoc as `@throws IllegalArgumentException (optional) if the comparator is found to violate the Comparator contract`. Read **"optional"** literally: the JDK makes no promise to detect a bad comparator. Most of the time it does not.

## 2\. How to Reproduce It (step-by-step)

The most common production cause is a comparator that never returns `0` — usually written as a one-liner during a code review cleanup.

```java
// BadComparator.java — java BadComparator.java (JDK 11+)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class BadComparator {

    static final class Job {
        final String id;
        final int priority;
        Job(String id, int priority) { this.id = id; this.priority = priority; }
        @Override public String toString() { return id + "(" + priority + ")"; }
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>();
        Random random = new Random(10);          // fixed seed: deterministic on every JDK
        for (int i = 0; i < 32; i++) {           // 32 == TimSort.MIN_MERGE
            jobs.add(new Job("job-" + i, random.nextInt(5)));
        }

        // BUG: never returns 0, so compare(a, b) == compare(b, a) == 1 for equal priorities
        Comparator<Job> byPriority = (a, b) -> a.priority < b.priority ? -1 : 1;

        jobs.sort(byPriority);
        System.out.println("sorted: " + jobs);
    }
}
```

```bash
# JDK 11+ single-file source launcher
java BadComparator.java

# Java 8
mkdir -p out && javac -d out BadComparator.java && java -cp out BadComparator
```

Both throw. `java.util.Random` is specified down to the algorithm, so seed `10` gives the identical 32 elements on 8, 11, 17, 21 and 25.

**Change `32` to `31` and the exception disappears** — the list is still mis-ordered (stability is destroyed inside each priority group), it just goes undetected. That threshold is `TimSort.MIN_MERGE = 32`.

A second, subtler cause is a *tolerance* comparator — "priorities within 5 of each other rank the same". It is not transitive: `10 ≈ 14`, `14 ≈ 18`, but `10 < 18`.

```java
Comparator<Job> fuzzy = (a, b) ->
    Math.abs(a.priority() - b.priority()) <= 5 ? 0 : Integer.compare(a.priority(), b.priority());
```

With 48 elements built from `new Random(43).nextInt(100)` this throws on JDK 8 and 21 alike. Note that it needs *more* data than the antisymmetry bug — non-transitivity has to line up with the run structure before TimSort notices.

**Environment triggers to be aware of:**

- Only fires at **32 elements or more**; below that TimSort runs binary insertion sort and never merges.
- Fires **data-dependently**: the same comparator sorts 10,000 lists fine and blows up on the 10,001st. This is why it shows up in production and never in your unit tests.
- Fires from **any** sort entry point, with different frames — worth knowing when you grep logs:

| Call site                                     | Distinguishing frame                                               |
| --------------------------------------------- | ------------------------------------------------------------------ |
| list.sort(cmp) / Collections.sort(list, cmp)  | java.util.ArrayList.sort                                           |
| Arrays.sort(array, cmp)                       | java.util.Arrays.sort(Arrays.java:1234)                            |
| stream().sorted(cmp)                          | java.util.stream.SortedOps$SizedRefSortingSink.end                 |
| parallelStream().sorted(cmp)                  | java.util.Arrays.parallelSort → SortedOps$OfRef.opEvaluateParallel |
| natural ordering (sort(null), Arrays.sort(a)) | java.util.ComparableTimSort.mergeLo                                |

`TreeSet`, `TreeMap` and `PriorityQueue` never throw this — they corrupt silently instead. A `TreeSet` built with the never-zero comparator above accepted all **4096** elements even though only 5 distinct priorities existed.

## 3\. Version Behaviour Matrix

| JDK           | Behaviour                                                                                                                                                                                                                                               |
| ------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 6 and earlier | Legacy merge sort. Bad comparators never detected; result silently wrong.                                                                                                                                                                               |
| 7             | TimSort introduced for object arrays (Arrays.sort(Object\[\]), Collections.sort). Error appears for the first time — the classic "worked on 6, broken on 7" upgrade report.                                                                             |
| 8             | Same message, no module prefix in frames. List.sort default method added in 8, so ArrayList.sort now appears in the trace.                                                                                                                              |
| 11            | Frames gain the java.base/ module prefix. TimSort.mergeLo moves to line 781.                                                                                                                                                                            |
| 17            | Identical behaviour; only Arrays.sort/ArrayList.sort line numbers move.                                                                                                                                                                                 |
| 21            | Identical. Records make it easy to write a *correct* comparator via Comparator.comparingInt(Job::priority).                                                                                                                                             |
| 25            | TimSort.java is byte-identical to 21\. Only change nearby: Arrays.LegacyMergeSort now reads the flag with Boolean.getBoolean(...) instead of AccessController.doPrivileged(...), after the Security Manager was permanently disabled (JEP 486, JDK 24). |

Separately, JDK-8072909 fixed a *different* TimSort failure — an `ArrayIndexOutOfBoundsException` in `pushRun`, caused by the pending-run stack being too small for worst-case inputs. The fix raised the stack from 40 to 49 entries for arrays ≥ 119,151 elements. Verified with `javap -p -c java.util.TimSort` on 8u482, 11.0.32, 17.0.20 and 21.0.10: all four allocate `5 / 10 / 24 / 49`, so the fix is in every JDK you are likely to run. That bug was a real JDK defect (proved by de Gouw et al., *"OpenJDK's java.utils.Collection.sort() is broken"*, CAV 2015). The `IllegalArgumentException` in this article is **not** a JDK bug — it is your comparator.

## 4\. Why It Happens — Surface Level

`Comparator` is not "a function returning a negative/zero/positive int". It is a contract that must define a **total order**. From the `Comparator` Javadoc:

> The implementor must ensure that `signum(compare(x, y)) == -signum(compare(y, x))` for all `x` and `y`. The implementor must also ensure that the relation is transitive: `((compare(x, y)>0) && (compare(y, z)>0))` implies `compare(x, z)>0`. Finally, the implementor must ensure that `compare(x, y)==0` implies that `signum(compare(x, z))==signum(compare(y, z))` for all `z`.

`(a, b) -> a.priority < b.priority ? -1 : 1` breaks the first rule: for two jobs with the same priority it returns `1` in both directions. TimSort takes that answer at face value, and its internal bookkeeping goes out of sync with the data.

The `IllegalArgumentException` is not a validation check. It is an **assertion failure** — TimSort noticed its own state was impossible and refused to keep writing into your array.

## 5\. Why It Happens — Under the Hood

TimSort (adapted from Tim Peters's Python list sort; `@author Josh Bloch`) works in three phases:

1. **Run detection.** `countRunAndMakeAscending` walks left to right finding a maximal ascending or strictly descending run, reversing descending ones in place (strictly descending, to keep the sort stable).
2. **Run extension.** Runs shorter than `minRunLength(n)` (between 16 and 32) are extended with `binarySort`, a binary insertion sort. For `n < MIN_MERGE` (32) the whole array is handled this way and **no merging happens at all** — that is exactly why 31 elements never throw.
3. **Merging.** Runs are pushed onto a stack and `mergeCollapse` merges them to maintain the invariant `runLen[i-1] > runLen[i] + runLen[i+1]` and `runLen[i] > runLen[i+1]`, which keeps run lengths balanced and bounds the stack depth.

The merge itself is where the failure surfaces. `mergeLo` copies the smaller (left) run into `tmp` and merges it back with the right run, tracking `len1` and `len2` — how many elements of each run remain. To go fast on structured data it switches into **galloping mode** after `MIN_GALLOP = 7` consecutive wins from one run, using `gallopRight`/`gallopLeft` (exponential search followed by binary search) to copy a whole block at once instead of comparing element by element.

Galloping is where the contract stops being a nicety. `gallopRight` binary-searches for an insertion point on the assumption that both runs are *sorted under the same total order*. If your comparator says `a > b` and also `b > a`, the binary search can return a position that skips or double-counts elements. The remaining-length counters then disagree with reality.

When the merge loop exits, TimSort checks what is left:

```java
if (len1 == 1) {
    System.arraycopy(a, cursor2, a, dest, len2);
    a[dest + len2] = tmp[cursor1];   // last elt of run 1 to end of merge
} else if (len1 == 0) {
    throw new IllegalArgumentException(
        "Comparison method violates its general contract!");
} else {
    assert len2 == 0;
    System.arraycopy(tmp, cursor1, a, dest, len1);
}
```

`len1 == 0` is structurally impossible for a valid comparator: `mergeLo` is only entered with `len1 >= 1`, and the loop breaks at `len1 == 1`. Reaching zero means the search consumed elements that were not there. TimSort throws rather than let `System.arraycopy` scribble past the end of the destination region.

This is why detection is **best-effort**: the exception fires only when the inconsistency happens to be visible to that specific check, on that specific data, after galloping engaged. A comparator built on `int` subtraction that overflows is just as illegal, and yet:

```java
Comparator<Integer> sub = (x, y) -> x - y;   // overflows for large-magnitude ints
```

Sorting 64 values from `new Random(7).nextInt()` with it produces **no exception and a wrongly ordered list**. Same for `(int)(a.timestamp() - b.timestamp())` narrowing a `long`. The exception is the *lucky* outcome; silent corruption is the common one.

## 6\. The Fix

### Fix 1 — make the comparator a total order (do this)

```diff
-Comparator<Job> byPriority = (a, b) -> a.priority < b.priority ? -1 : 1;
+Comparator<Job> byPriority = Comparator.comparingInt(Job::priority);
```

`Comparator.comparingInt` (Java 8+) delegates to `Integer.compare`, which is antisymmetric, transitive, and returns `0` for equals. For a `long` or `double` key use `comparingLong` / `comparingDouble` — never subtraction, never a cast.

If you needed the never-zero behaviour because you wanted a deterministic order among equal priorities, express that as a **tiebreaker**, not as a lie:

```java
record Job(String id, int priority, long submittedAt) {}

static final Comparator<Job> BY_PRIORITY =
        Comparator.comparingInt(Job::priority)
                  .thenComparingLong(Job::submittedAt)
                  .thenComparing(Job::id);   // id is unique -> strict total order
```

### Fix 2 — for the tolerance comparator, bucket first

Fuzzy equality can never be a total order. Quantise into buckets, then compare buckets:

```diff
-Comparator<Job> fuzzy = (a, b) ->
-    Math.abs(a.priority() - b.priority()) <= 5 ? 0 : Integer.compare(a.priority(), b.priority());
+// bucket width 5: equality is now transitive because it is equality of an int
+Comparator<Job> banded =
+    Comparator.comparingInt((Job j) -> j.priority() / 5)
+              .thenComparing(Job::id);
```

### Fix 3 — the escape hatch you should not ship

```bash
java -Djava.util.Arrays.useLegacyMergeSort=true -cp out BadComparator
```

This switches `Arrays.sort(Object[], Comparator)` back to the pre-Java-7 merge sort. It still works on JDK 25, and the JDK source still carries the comment `/** To be removed in a future release. */`. Understand what it buys you: on the reproducer above it prints a result — with the equal-priority groups in **reverse** insertion order, i.e. silently unstable and wrong. It also does **not** cover `Arrays.parallelSort` or `parallelStream().sorted()`, which still throw. Use it for one release while you find the real comparator, never as the fix.

## 7\. Best Practices & The Better Design

- **Never hand-write `?:` comparators.** `Comparator.comparing*` \+ `thenComparing` \+ `reversed()` \+ `nullsFirst`/`nullsLast` composes correctly by construction and reads better.
- **Never subtract.** `a - b` is only safe when both operands are known small non-negative ints. Use `Integer.compare` / `Long.compare` / `Double.compare`.
- **Never compare on mutable state.** A comparator reading a field that another thread mutates mid-sort produces exactly this exception, non-deterministically. Sort a snapshot of immutable value objects — this is what `record` is for.
- **Keep the comparator consistent with `equals`** when the objects will also land in a `TreeSet`/`TreeMap`, or accept the "strange" behaviour the `Comparator` Javadoc warns about.
- **Sort once, at the edge.** If ordering matters to a client, produce it with a single named `static final Comparator<T>` constant that is unit-tested, rather than inline lambdas scattered across services.

```java
record Job(String id, int priority, long submittedAt) {}

static final Comparator<Job> BY_PRIORITY_THEN_AGE =
        Comparator.comparingInt(Job::priority)
                  .thenComparingLong(Job::submittedAt)
                  .thenComparing(Job::id);

List<Job> ordered = jobs.stream().sorted(BY_PRIORITY_THEN_AGE).toList();
```

## 8\. How to Prevent It Long-Term

**Test the contract, not the output.** A three-nested-loop brute force over a small sample catches every violation this article covers:

```java
public static <T> void assertTotalOrder(List<T> sample, Comparator<? super T> c) {
    for (T x : sample) {
        for (T y : sample) {
            int xy = Integer.signum(c.compare(x, y));
            if (xy != -Integer.signum(c.compare(y, x))) {
                throw new AssertionError("antisymmetry broken for " + x + ", " + y);
            }
            for (T z : sample) {
                if (xy > 0 && Integer.signum(c.compare(y, z)) > 0
                        && Integer.signum(c.compare(x, z)) <= 0) {
                    throw new AssertionError("transitivity broken: " + x + " " + y + " " + z);
                }
            }
        }
    }
}
```

Feed it a sample with **deliberate duplicates** — `List.of(1, 1, 2, 3, 3, 4)` is enough to catch the never-zero bug. Better still, drive it with jqwik or a Guava `Ordering` property test so the sample is generated.

**Other guardrails:**

- Sort **at least 40 elements** in the test that exercises a comparator. Anything under 32 cannot reach the merge path.
- Static analysis: Error Prone's `ComparisonContractViolated` and `SelfComparison`, plus SpotBugs' `CO_COMPARETO_RESULTS_MIN_VALUE` and `RV_NEGATING_RESULT_OF_COMPARETO`, catch the subtraction and `Integer.MIN_VALUE` variants in CI. Run `javac -Xlint:all -Werror`.
- Production diagnostics: enable the JFR exception events so you capture the offending payload, not just the frame.

```bash
java -XX:StartFlightRecording=filename=app.jfr,settings=profile \
     -XX:+HeapDumpOnOutOfMemoryError -jar app.jar
# or attach to a running JVM
jcmd <pid> JFR.start name=cmp settings=profile filename=/tmp/cmp.jfr
jfr summary /tmp/cmp.jfr | grep -i exception
```

`jdk.JavaExceptionThrow` records the stack for every thrown exception, which turns "it happens once a week" into a reproducible input set.

- Because the failure is data-dependent, add the comparator's inputs to the log line at the catch site. A bare stack trace tells you nothing you cannot already read here.

**Related failure modes worth linking:** a comparator inconsistent with `equals` breaks `TreeMap`/`TreeSet` lookups the same way a broken `hashCode` breaks `HashMap`; mutating an element mid-sort is the same class of bug as mutating a `HashMap` key after insertion; and sorting a `List.of(...)` result will hand you `UnsupportedOperationException` before TimSort ever runs.

## 9\. Key Takeaways

- **`IllegalArgumentException: Comparison method violates its general contract!` is a TimSort assertion, not a validator.** It fires when `mergeLo` finds `len1 == 0`, which is impossible for a legal comparator. Silent wrong ordering is far more common than the exception.
- **The threshold is 32 elements** (`TimSort.MIN_MERGE`). Below that, binary insertion sort runs and no violation is ever detected — so size your comparator tests accordingly.
- **The three rules are antisymmetry, transitivity, and equality substitution.** The two comparators that break them in real code are "never returns 0" (`a < b ? -1 : 1`) and "close enough counts as equal".
- **Fix it with `Comparator.comparingInt(...).thenComparing(...)`**, never with subtraction or a hand-rolled ternary; add a tiebreaker instead of refusing to return 0.
- **`-Djava.util.Arrays.useLegacyMergeSort=true` is a stopgap, not a fix.** It still works on JDK 25, it silences the exception, it returns wrongly ordered data, and it does not cover `parallelSort`.