Comparison Method Violates Its General Contract in Java

1. The Error

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:

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.

// 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);
    }
}

# 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.

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:

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

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:

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:

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)

-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:

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:

-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

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.

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:

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.

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.