[Advanced Java] Comparable vs Comparator in Java: Natural Ordering and Custom Sorting

Sorting in Java splits into two questions that look alike and are not. The first is what order a type has when nobody says otherwise: that is Comparable, it lives inside the class, and a class gets exactly one. The second is what order this particular call wants: that is Comparator, it lives outside the class, and you can have as many as you can name.

Everything difficult about custom sorting follows from that split, plus one thing neither interface can enforce. A comparison method has a contract, the compiler cannot check it, and when you break it the JDK sometimes throws and sometimes just hands back the wrong answer.

Every listing, error message, stack trace and count below was produced by compiling and running the code on OpenJDK 21.0.6 (arm64). Cost is always expressed as instrumented counts of compare() invocations, never as elapsed time — a counter returns the same number on every machine and a stopwatch does not.

Comparable: the ordering the type owns

Comparable<T> has one method, int compareTo(T o), and implementing it declares the type's natural ordering. The return value carries a sign, not a magnitude: negative means "this comes first", zero means "these tie", positive means "this comes second".

A version number is the standard case, because sorting versions as text is famously wrong:

import java.util.*;

class Version implements Comparable<Version> {
    final int major, minor, patch;

    Version(int major, int minor, int patch) {
        this.major = major; this.minor = minor; this.patch = patch;
    }

    @Override
    public int compareTo(Version o) {
        int c = Integer.compare(major, o.major);
        if (c != 0) return c;
        c = Integer.compare(minor, o.minor);
        if (c != 0) return c;
        return Integer.compare(patch, o.patch);
    }

    @Override public boolean equals(Object o) {
        return o instanceof Version v && major == v.major && minor == v.minor && patch == v.patch;
    }
    @Override public int hashCode() { return Objects.hash(major, minor, patch); }
    @Override public String toString() { return major + "." + minor + "." + patch; }
}

public class NaturalOrder {
    public static void main(String[] args) {
        List<Version> vs = new ArrayList<>(List.of(
            new Version(1, 10, 0), new Version(1, 2, 3),
            new Version(2, 0, 0), new Version(1, 2, 10)));
        System.out.println("before = " + vs);
        Collections.sort(vs);
        System.out.println("after  = " + vs);

        System.out.println("compareTo sign  = " + new Version(1,2,3).compareTo(new Version(1,10,0)));
        System.out.println("as strings sort = " + new TreeSet<>(List.of("1.10.0","1.2.3","2.0.0","1.2.10")));
    }
}

before = [1.10.0, 1.2.3, 2.0.0, 1.2.10]
after  = [1.2.3, 1.2.10, 1.10.0, 2.0.0]
compareTo sign  = -1
as strings sort = [1.10.0, 1.2.10, 1.2.3, 2.0.0]

The last line is why the class exists at all. Compared as text, 1.10.0 sorts before 1.2.3, because 1 is a smaller character than 2. Compared by the natural ordering the type defines, it does not.

A type without a natural ordering cannot be sorted without one. Collections.sort is declared as <T extends Comparable<? super T>>, so the failure is a compile error rather than a surprise at runtime:

NotComparable.java:9: error: no suitable method found for sort(List<Point>)
        Collections.sort(pts);
                   ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Point
        upper bounds: Comparable<? super T#1>)

List.sort is the weaker door. It accepts null to mean "use natural ordering", the parameter is a plain Comparator<? super E> with no Comparable bound, and so list.sort(null) on a type that is not Comparable compiles and blows up at runtime:

Exception in thread "main" java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable (Point is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.base/java.util.Arrays.sort(Arrays.java:1108)
	at java.base/java.util.Arrays.sort(Arrays.java:1302)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at RawSort.main(RawSort.java:9)

One natural ordering per class, and the compiler enforces it

"One per class" is not a style guideline. Because generic type arguments are erased, a class cannot implement Comparable twice with different arguments, and javac rejects it outright:

class Money implements Comparable<Money>, Comparable<String> {
    public int compareTo(Money o) { return 0; }
    public int compareTo(String o) { return 0; }
}

TwoNatural.java:1: error: repeated interface
class Money implements Comparable<Money>, Comparable<String> {
                                                    ^
TwoNatural.java:1: error: Comparable cannot be inherited with different arguments: <Money> and <java.lang.String>
class Money implements Comparable<Money>, Comparable<String> {
^
2 errors

So the moment you need a second ordering, Comparable is finished and Comparator starts.

The compareTo contract

compareTo is a method the JDK calls on your behalf inside sorted collections and sorting algorithms, and those algorithms assume it behaves like a real ordering. The contract in the javadoc has four parts, and only the last is optional.

compareTo must also throw NullPointerException for a null argument and ClassCastException for a type it cannot compare. Both are the JDK's own behaviour, not something you add.

The first three rules are checkable on a sample, and it is worth writing the checker once because it turns "this comparator feels wrong" into a concrete failing triple:

import java.util.*;

public class ContractCheck {
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    static <T> String check(Comparator<T> c, List<T> xs) {
        for (T a : xs) for (T b : xs) {
            if (Integer.signum(c.compare(a, b)) != -Integer.signum(c.compare(b, a)))
                return "sign symmetry fails at (" + a + ", " + b + ")";
        }
        for (T a : xs) for (T b : xs) for (T d : xs) {
            if (c.compare(a, b) > 0 && c.compare(b, d) > 0 && !(c.compare(a, d) > 0))
                return "transitivity fails at (" + a + ", " + b + ", " + d + ")";
            if (c.compare(a, b) == 0
                && Integer.signum(c.compare(a, d)) != Integer.signum(c.compare(b, d)))
                return "equality transitivity fails at (" + a + ", " + b + ", " + d + ")";
        }
        return "holds on this sample";
    }

    public static void main(String[] args) {
        List<Integer> xs = List.of(0, 5, 8, 12, 16, 25, 40);
        System.out.println("naturalOrder : " + check(Comparator.<Integer>naturalOrder(), xs));
        System.out.println("TOLERANT     : " + check(TOLERANT, xs));

        System.out.println();
        System.out.println("String.compareTo returns a magnitude, not just -1/0/1:");
        System.out.println("  \"apple\".compareTo(\"banana\") = " + "apple".compareTo("banana"));
        System.out.println("  \"a\".compareTo(\"z\")          = " + "a".compareTo("z"));
        System.out.println("  \"abc\".compareTo(\"ab\")       = " + "abc".compareTo("ab"));
        System.out.println("  Integer.compare(3, 99)      = " + Integer.compare(3, 99));

        System.out.println();
        try { "a".compareTo(null); } catch (Exception e) { System.out.println("  compareTo(null) -> " + e); }
    }
}

naturalOrder : holds on this sample
TOLERANT     : equality transitivity fails at (0, 5, 12)

String.compareTo returns a magnitude, not just -1/0/1:
  "apple".compareTo("banana") = -1
  "a".compareTo("z")          = -25
  "abc".compareTo("ab")       = 1
  Integer.compare(3, 99)      = -1

  compareTo(null) -> java.lang.NullPointerException: Cannot read field "value" because "anotherString" is null

Two facts fall out of that run. First, the "within 10 counts as equal" comparator — which reads perfectly sensible — already fails on a seven-element sample. Second, String.compareTo returns -25, not -1: the magnitude is an implementation detail nobody promises, so never test a comparison result for == -1 or == 1. Test the sign.

Consistency with equals is a recommendation, not a rule

The fourth rule is the odd one. The javadoc says a natural ordering consistent with equals is strongly recommended but not required, and the JDK will not stop you writing one that is not — BigDecimal ships one, since 2.0 and 2.00 are equal by compareTo and unequal by equals.

The place where "not required" turns into lost data is sorted collections, which decide duplicates by compareTo rather than by equals; a sibling article in this series builds that case and counts the elements that disappear. For plain list sorting the inconsistency is harmless, and that is the whole distinction.

Comparator: the ordering the caller owns

Comparator<T> declares int compare(T a, T b) with the same sign convention, and takes both operands as arguments instead of using this. That one difference is the whole design: a comparator is a value, so it can be stored in a field, passed to a method, returned from a factory, and chosen at the call site.

It has a single abstract method, so a lambda or a method reference is a Comparator — that is all this article needs from functional interfaces. The important part is that nothing here touches the class being sorted:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class ThreeOrderings {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana",  "Eng",   120),
        new Employee("Bo",   "Sales", 120),
        new Employee("Cy",   "Eng",   140),
        new Employee("Dee",  "Sales", 110));

    public static void main(String[] args) {
        Comparator<Employee> byName    = comparing(Employee::name);
        Comparator<Employee> byPay     = comparingInt(Employee::salary).reversed();
        Comparator<Employee> byDeptPay = comparing(Employee::dept).thenComparingInt(Employee::salary);

        for (Comparator<Employee> c : List.of(byName, byPay, byDeptPay)) {
            List<Employee> l = new ArrayList<>(STAFF);
            l.sort(c);
            System.out.println(l);
        }
    }
}

[Ana/Eng/120, Bo/Sales/120, Cy/Eng/140, Dee/Sales/110]
[Cy/Eng/140, Ana/Eng/120, Bo/Sales/120, Dee/Sales/110]
[Ana/Eng/120, Cy/Eng/140, Dee/Sales/110, Bo/Sales/120]

Three orderings, one record, and Employee does not know any of them exist.

The factory and combinator API

Almost nobody writes new Comparator<Employee>() { ... } any more, and almost nobody should write a bare two-argument lambda either. The static factories build a comparator from a key, and the default methods compose comparators into bigger ones.

Two properties of this list matter more than the list itself. Every one of these returns a new comparator and mutates nothing, and every combinator wraps the comparator it was invoked on rather than the last key you named.

Why comparingInt, comparingLong and comparingDouble exist

comparing takes a Function<T, U extends Comparable<? super U>>, and int is not a Comparable. So a key extractor that returns int gets autoboxed on every call, and the JDK's own implementation then calls compareTo on the box:

public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
        Function<? super T, ? extends U> keyExtractor)
{
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
}

public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}

comparingInt takes a ToIntFunction instead, so the key never becomes an object. The difference is visible in the bytecode of the two lambdas, not just in the signatures:

import java.util.*;

record Employee(String name, String dept, int salary) {}

public class Boxing {
    public static void main(String[] args) {
        List<Employee> l = new ArrayList<>();
        l.sort(Comparator.comparing((Employee e) -> e.salary()));
        l.sort(Comparator.comparingInt((Employee e) -> e.salary()));
    }
}

javap -p -c Boxing

  private static int lambda$main$1(Employee);
    Code:
       0: aload_0
       1: invokevirtual #34                 // Method Employee.salary:()I
       4: ireturn

  private static java.lang.Integer lambda$main$0(Employee);
    Code:
       0: aload_0
       1: invokevirtual #34                 // Method Employee.salary:()I
       4: invokestatic  #40                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
       7: areturn

Same source expression, two return types. The comparing version ends in Integer.valueOf; the comparingInt version ends in ireturn. Salaries above 127 fall outside the Integer cache, so each of those valueOf calls really does allocate.

The key extractor runs twice per comparison

How often does that happen? Once per operand per comparison, which is a number you can count rather than guess:

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;

record Employee(String name, String dept, int salary) {}

public class BoxCount {
    public static void main(String[] args) {
        Random r = new Random(7);
        List<Employee> base = new ArrayList<>();
        for (int i = 0; i < 1000; i++) base.add(new Employee("e" + i, "d", r.nextInt(1_000_000)));

        AtomicLong k1 = new AtomicLong(), k2 = new AtomicLong();
        List<Employee> a = new ArrayList<>(base);
        a.sort(Comparator.comparing((Employee e) -> { k1.incrementAndGet(); return e.salary(); }));
        List<Employee> b = new ArrayList<>(base);
        b.sort(Comparator.comparingInt((Employee e) -> { k2.incrementAndGet(); return e.salary(); }));

        System.out.printf("comparing    : %,d key-extractor calls, %,d Integer boxes%n", k1.get(), k1.get());
        System.out.printf("comparingInt : %,d key-extractor calls, 0 Integer boxes%n", k2.get());
        System.out.println("same order   : " + a.equals(b));
    }
}

comparing    : 17,346 key-extractor calls, 17,346 Integer boxes
comparingInt : 17,346 key-extractor calls, 0 Integer boxes
same order   : true

Sorting a thousand records performed 8,673 comparisons, so the key extractor ran 17,346 times either way. With comparing that is 17,346 allocations for nothing. The same arithmetic is the real argument against an expensive key extractor: comparing(e -> e.name().toLowerCase()) builds seventeen thousand strings to sort a thousand records, and the fix is to store the normalised key on the object rather than to compute it inside the comparator.

The inference trap in a chained lambda

One thing about this API bites everyone once. A lambda with an inferred parameter type needs a target type, and the receiver of a chained call does not have one:

import java.util.*;

record Employee(String name, String dept, int salary) {}

public class Infer {
    public static void main(String[] args) {
        List<Employee> l = new ArrayList<>();
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
    }
}

Infer.java:8: error: cannot find symbol
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
                                          ^
  symbol:   method dept()
  location: variable e of type Object
Infer.java:8: error: cannot find symbol
        l.sort(Comparator.comparing(e -> e.dept()).thenComparing(e -> e.name()));
                                                                       ^
  symbol:   method name()
  location: variable e of type Object
2 errors

e inferred as Object. Without the chain, the same lambda compiles fine, because l.sort(...) supplies the target type. Either name the parameter type once or use a method reference:

l.sort(Comparator.comparing((Employee e) -> e.dept()).thenComparing(e -> e.name()));
l.sort(Comparator.comparing(Employee::dept).thenComparing(Employee::name));

Chaining, and what reversed() actually reverses

thenComparing builds a composite: run the first comparator, and if it returns zero, run the second. reversed() flips a comparator. The trap is that by the time you call reversed() on a chain, the comparator it is flipping is the entire chain.

Four orderings of the same five records, all real output:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class Chaining {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana",  "Eng",   120),
        new Employee("Bo",   "Sales", 120),
        new Employee("Cy",   "Eng",   140),
        new Employee("Dee",  "Sales", 110),
        new Employee("Eli",  "Eng",   120));

    static void show(String label, Comparator<Employee> c) {
        List<Employee> l = new ArrayList<>(STAFF);
        l.sort(c);
        System.out.println(label);
        l.forEach(e -> System.out.println("    " + e));
    }

    public static void main(String[] args) {
        show("A  comparing(dept).thenComparing(salary)",
             comparing(Employee::dept).thenComparing(Employee::salary));

        show("B  comparing(dept).thenComparing(salary).reversed()",
             comparing(Employee::dept).thenComparing(Employee::salary).reversed());

        show("C  comparing(dept).thenComparing(comparing(salary).reversed())",
             comparing(Employee::dept).thenComparing(comparing(Employee::salary).reversed()));

        show("D  comparing(dept).thenComparing(salary, reverseOrder())",
             comparing(Employee::dept).thenComparing(Employee::salary, reverseOrder()));
    }
}

A  comparing(dept).thenComparing(salary)
    Ana/Eng/120
    Eli/Eng/120
    Cy/Eng/140
    Dee/Sales/110
    Bo/Sales/120
B  comparing(dept).thenComparing(salary).reversed()
    Bo/Sales/120
    Dee/Sales/110
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
C  comparing(dept).thenComparing(comparing(salary).reversed())
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
    Bo/Sales/120
    Dee/Sales/110
D  comparing(dept).thenComparing(salary, reverseOrder())
    Cy/Eng/140
    Ana/Eng/120
    Eli/Eng/120
    Bo/Sales/120
    Dee/Sales/110

Read B against D. Almost everyone who writes B wants D: departments in their usual order, highest paid first inside each one. What B produced is Sales before Eng — the department key was flipped as well, because reversed() was applied to the composite, not to the last key mentioned. C and D are the two ways to reverse only the trailing key, and D is the shorter one.

The rule is mechanical: reversed() reverses the comparator it is called on, and method chaining means that comparator is everything to its left.

reversed() is not the same as sorting and flipping the list

There is a second, quieter difference. Reversing a comparator does not reverse the order of elements that tie, because the sort is stable either way — but reversing the finished list does:

import java.util.*;
import static java.util.Comparator.*;

record Employee(String name, String dept, int salary) {
    @Override public String toString() { return name + "/" + dept + "/" + salary; }
}

public class ReversedStable {
    static final List<Employee> STAFF = List.of(
        new Employee("Ana", "Eng",   120),
        new Employee("Bo",  "Sales", 120),
        new Employee("Cy",  "Eng",   140),
        new Employee("Dee", "Sales", 110),
        new Employee("Eli", "Eng",   120));

    public static void main(String[] args) {
        List<Employee> a = new ArrayList<>(STAFF);
        a.sort(comparingInt(Employee::salary).reversed());
        System.out.println("sort with reversed()      = " + a);

        List<Employee> b = new ArrayList<>(STAFF);
        b.sort(comparingInt(Employee::salary));
        System.out.println("sort ascending then flip  = " + b.reversed());
    }
}

sort with reversed()      = [Cy/Eng/140, Ana/Eng/120, Bo/Sales/120, Eli/Eng/120, Dee/Sales/110]
sort ascending then flip  = [Cy/Eng/140, Eli/Eng/120, Bo/Sales/120, Ana/Eng/120, Dee/Sales/110]

Three employees earn 120. Sorting with reversed() leaves them in Ana, Bo, Eli — their original order. Sorting ascending and reversing the whole list leaves them in Eli, Bo, Ana. If your list came out of a previous sort or a database ORDER BY, those two are not interchangeable. (List.reversed() used above is the SequencedCollection view added in Java 21; it returns a reversed view, so it costs nothing to build.)

The subtraction bug

The oldest comparator in Java is (a, b) -> a.value - b.value, and it is wrong. Subtraction of two int values overflows silently, and when it does the sign of the result is the opposite of the truth:

import java.util.*;

record Account(String id, int balance) {
    @Override public String toString() { return id + "=" + balance; }
}

public class Overflow {
    public static void main(String[] args) {
        List<Account> accounts = new ArrayList<>(List.of(
            new Account("a", 2_000_000_000),
            new Account("b", -2_000_000_000),
            new Account("c", 0)));

        List<Account> broken = new ArrayList<>(accounts);
        broken.sort((x, y) -> x.balance() - y.balance());
        System.out.println("subtraction     = " + broken);

        List<Account> fixed = new ArrayList<>(accounts);
        fixed.sort(Comparator.comparingInt(Account::balance));
        System.out.println("Integer.compare = " + fixed);

        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println();
        System.out.println("  a - b           = " + (a - b));
        System.out.println("  Integer.compare = " + Integer.compare(a, b));
        System.out.println("  a > b           = " + (a > b));
    }
}

subtraction     = [a=2000000000, b=-2000000000, c=0]
Integer.compare = [b=-2000000000, c=0, a=2000000000]

  a - b           = -294967296
  Integer.compare = 1
  a > b           = true

2000000000 - (-2000000000) is 4,000,000,000, which does not fit in an int; it wraps to -294967296, so the comparator reports that two billion is less than minus two billion. The list came back in its original order and nothing complained.

This is only safe when both operands are known to be non-negative and their difference cannot exceed Integer.MAX_VALUE — sizes, counts, indices. That precondition is easy to state and easy to lose during a refactor, and Integer.compare(x, y) costs nothing, so there is no reason to keep the subtraction. The same argument applies to Long.compare, Double.compare and Character.compare; Double.compare additionally gets NaN and -0.0 right, which no arithmetic expression will.

Comparison method violates its general contract

Here is the failure this whole article is really about. A comparator that is not transitive can survive every test you write and then take down a production request, because the JDK only notices on inputs large enough to reach a particular code path.

The classic non-transitive comparator is a tolerance: values within some distance count as equal.

import java.util.*;

public class Tolerant {
    // "within 10 counts as equal" -- reads sensible, is not transitive
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    public static void main(String[] args) {
        System.out.println("cmp(0, 8)   = " + TOLERANT.compare(0, 8));
        System.out.println("cmp(8, 16)  = " + TOLERANT.compare(8, 16));
        System.out.println("cmp(0, 16)  = " + TOLERANT.compare(0, 16));
    }
}

cmp(0, 8)   = 0
cmp(8, 16)  = 0
cmp(0, 16)  = -1

0 equals 8, 8 equals 16, and 0 is less than 16. Nothing that reasons about ordering can survive that, because "equal" is no longer an equivalence relation.

Where the check lives, and why 32 is the number

List.sort on an ArrayList reaches java.util.TimSort, and TimSort has two different modes. Below MIN_MERGE it does one binary insertion pass and stops. Only above it does it build runs and merge them, and the contract check lives inside those merges:

private static final int MIN_MERGE = 32;

// ...

int nRemaining  = hi - lo;
if (nRemaining < 2)
    return;  // Arrays of size 0 and 1 are always sorted

// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
    int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
    binarySort(a, lo, hi, lo + initRunLen, c);
    return;
}

The exception itself is thrown from mergeLo and mergeHi, at the point where one of the two runs being merged is found to be exhausted while the merge still believes elements remain. That state is unreachable with a well-behaved comparator, so TimSort concludes — correctly — that the comparator is the problem, and reports it rather than corrupting the array.

Same comparator, one element more

The consequence is that the same broken comparator behaves completely differently depending on how much data you hand it. This program takes the size on the command line and builds its input from a fixed seed, so every run below is reproducible:

import java.util.*;

public class ContractViolation {
    static final Comparator<Integer> TOLERANT =
        (a, b) -> Math.abs(a - b) <= 10 ? 0 : Integer.compare(a, b);

    static List<Integer> sample(int n) {
        Random rnd = new Random(42);
        List<Integer> l = new ArrayList<>();
        for (int i = 0; i < n; i++) l.add(rnd.nextInt(200));
        return l;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        List<Integer> l = sample(n);
        l.sort(TOLERANT);
        System.out.println("n=" + n + " sorted without throwing");
        System.out.println("ascending? " + ascending(l));
        System.out.println("first 20  = " + l.subList(0, Math.min(20, l.size())));
    }

    static boolean ascending(List<Integer> l) {
        for (int i = 1; i < l.size(); i++) if (l.get(i - 1) > l.get(i)) return false;
        return true;
    }
}

At n = 32 there is no exception, and no sorted list either:

n=32 sorted without throwing
ascending? false
first 20  = [9, 0, 32, 26, 30, 48, 43, 41, 56, 46, 63, 58, 84, 76, 76, 93, 105, 102, 92, 118]

9 before 0, 32 before 26, 48 before 43. This is the outcome a unit test with a handful of fixtures gets: a result that is roughly sorted, plausible at a glance, and wrong.

At n = 122 — the same comparator, the same generator, one element more than n = 121, which still returns quietly — the sort refuses:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
	at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
	at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
	at java.base/java.util.TimSort.sort(TimSort.java:254)
	at java.base/java.util.Arrays.sort(Arrays.java:1308)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at ContractViolation.main(ContractViolation.java:17)

Running every size from 2 to 1000 through that generator and recording which ones threw gives the shape of the problem:

⚠️ The bug does not get worse as n grows. It is equally present at n = 4. What grows is the probability that TimSort's merge phase happens to walk into the inconsistency and tell you about it — which is exactly why this arrives as a production incident rather than a failing test.

Nothing in the exception names your comparator, either. When you see this stack trace, the method at fault is whatever comparator was passed to that sort call, and finding it means re-reading every compare on the path.

The system property that hides it

Arrays still carries the pre-Java-7 merge sort behind a system property, and that implementation has no check:

java -Djava.util.Arrays.useLegacyMergeSort=true ContractViolation 500

n=500 sorted without throwing
ascending? false
first 20  = [9, 0, 1, 0, 3, 2, 3, 0, 6, 6, 17, 12, 7, 10, 3, 7, 6, 6, 19, 10]

The exception is gone and the data is still wrong. This flag exists so that code written against Java 6 keeps starting up; using it to make an IllegalArgumentException disappear trades a loud failure for a silent one.

Fixing it: make "equal" an equivalence relation

The repair is not to loosen the comparator, it is to make ties genuinely transitive. Instead of "these two are close", ask "do these two land in the same bucket", which is a question with a single answer per value:

import java.util.*;

public class Bucketed {
    // transitive: two values are equal iff they land in the same bucket
    static final Comparator<Integer> BUCKETED = Comparator.comparingInt(v -> v / 10);

    public static void main(String[] args) {
        System.out.println("cmp(0, 8)  = " + BUCKETED.compare(0, 8));
        System.out.println("cmp(8, 16) = " + BUCKETED.compare(8, 16));
        System.out.println("cmp(0, 16) = " + BUCKETED.compare(0, 16));

        for (int n : new int[]{122, 500, 1000, 100000}) {
            Random rnd = new Random(42);
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < n; i++) l.add(rnd.nextInt(200));
            l.sort(BUCKETED);
            boolean ok = true;
            for (int i = 1; i < l.size(); i++) if (l.get(i-1) / 10 > l.get(i) / 10) ok = false;
            System.out.println("n=" + n + " sorted, buckets ascending = " + ok);
        }
    }
}

cmp(0, 8)  = 0
cmp(8, 16) = -1
cmp(0, 16) = -1
n=122 sorted, buckets ascending = true
n=500 sorted, buckets ascending = true
n=1000 sorted, buckets ascending = true
n=100000 sorted, buckets ascending = true

8 and 16 are now different, which is less forgiving than the tolerance version and is the price of an ordering that exists. The general form of the fix: derive a key from each element, and compare the keys. Any comparator built out of comparing, comparingInt and thenComparing over pure key extractors is transitive by construction, which is a good reason to prefer them over hand-written compare bodies.

null keys: nullsFirst and nullsLast

comparing calls compareTo on whatever the key extractor returns, so a null key is a NullPointerException inside the sort:

import java.util.*;
import static java.util.Comparator.*;

record Contact(String name, String nickname) {
    @Override public String toString() { return name + "(" + nickname + ")"; }
}

public class Nulls {
    public static void main(String[] args) {
        List<Contact> cs = new ArrayList<>(List.of(
            new Contact("Ana", "ana"), new Contact("Bo", "bo")));
        cs.add(new Contact("Cy", null));

        try {
            List<Contact> l = new ArrayList<>(cs);
            l.sort(comparing(Contact::nickname));
        } catch (Exception e) {
            System.out.println("comparing(nickname)                 -> " + e);
        }

        List<Contact> a = new ArrayList<>(cs);
        a.sort(comparing(Contact::nickname, nullsFirst(naturalOrder())));
        System.out.println("nullsFirst(naturalOrder())          -> " + a);

        List<Contact> b = new ArrayList<>(cs);
        b.sort(comparing(Contact::nickname, nullsLast(naturalOrder())));
        System.out.println("nullsLast(naturalOrder())           -> " + b);

        List<String> raw = new ArrayList<>(Arrays.asList("b", null, "a", null, "c"));
        raw.sort(nullsFirst(naturalOrder()));
        System.out.println("List<String> nullsFirst             -> " + raw);
        raw.sort(nullsLast(reverseOrder()));
        System.out.println("List<String> nullsLast(reverseOrder)-> " + raw);
    }
}

comparing(nickname)                 -> java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because the return value of "java.util.function.Function.apply(Object)" is null
nullsFirst(naturalOrder())          -> [Cy(null), Ana(ana), Bo(bo)]
nullsLast(naturalOrder())           -> [Ana(ana), Bo(bo), Cy(null)]
List<String> nullsFirst             -> [null, null, a, b, c]
List<String> nullsLast(reverseOrder)-> [c, b, a, null, null]

Two things worth noting. The two-argument comparing(keyExtractor, keyComparator) is where the null-tolerant comparator belongs — wrapping the outer comparator in nullsFirst would only protect against null elements, not null keys. And nullsFirst/nullsLast decide only where the nulls go; the comparator you pass them still decides everything else, which is why nullsLast(reverseOrder()) puts null after a even though the rest of the list is descending.

Stability, and what it buys you

A sort is stable when elements that compare equal keep the relative order they already had. List.sort and Arrays.sort(Object[], Comparator) are stable — both run TimSort, and the javadoc states the guarantee. That is what makes a two-pass sort work:

import java.util.*;
import static java.util.Comparator.*;

record Ticket(String title, String assignee, int priority) {
    @Override public String toString() { return priority + " " + assignee + " " + title; }
}

public class Stability {
    public static void main(String[] args) {
        List<Ticket> t = new ArrayList<>(List.of(
            new Ticket("crash on save", "bo",  1),
            new Ticket("slow startup",  "ana", 2),
            new Ticket("typo in menu",  "cy",  2),
            new Ticket("data loss",     "ana", 1),
            new Ticket("bad icon",      "bo",  2)));

        t.sort(comparing(Ticket::title));
        System.out.println("after pass 1 (title):");
        t.forEach(x -> System.out.println("    " + x));

        t.sort(comparingInt(Ticket::priority));
        System.out.println("after pass 2 (priority):");
        t.forEach(x -> System.out.println("    " + x));
    }
}

after pass 1 (title):
    2 bo bad icon
    1 bo crash on save
    1 ana data loss
    2 ana slow startup
    2 cy typo in menu
after pass 2 (priority):
    1 bo crash on save
    1 ana data loss
    2 bo bad icon
    2 ana slow startup
    2 cy typo in menu

The second pass only mentions priority, and the titles inside each priority group are still alphabetical. That is stability doing work: sort by the least significant key first, then by the most significant, and you get a multi-key ordering without composing a comparator. thenComparing is usually clearer and always cheaper — one pass instead of two — but the two-pass form is what you need when the passes happen in different places, such as a database returning rows in one order and the UI regrouping them in another.

Primitive arrays take no comparator at all

Arrays.sort on a primitive array is a dual-pivot quicksort and is not stable, but that is not a limitation you can run into, because there is no overload that would let you observe it:

int[] a = {5, 1, 4};
Arrays.sort(a, Comparator.reverseOrder());

PrimSort.java:5: error: no suitable method found for sort(int[],Comparator<T#1>)
        Arrays.sort(a, Comparator.reverseOrder());
              ^
    method Arrays.<T#2>sort(T#2[],Comparator<? super T#2>) is not applicable
      (inference variable T#2 has incompatible bounds
        equality constraints: int
        upper bounds: Object)

Two equal int values are the same value; no program can tell which one moved. Stability is meaningful only when equal elements are distinguishable, which requires objects. To sort primitives by a custom order you must box first — Arrays.stream(a).boxed().toArray(Integer[]::new) and then Arrays.sort(boxed, cmp) — and pay for the boxing.

Counting comparisons instead of timing them

TimSort is adaptive: it finds runs that are already ordered and merges them instead of re-sorting them. Counting compare() invocations shows that far better than a stopwatch, and gives the same answer on every machine:

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;

public class Counts {
    static AtomicLong compares = new AtomicLong();

    static Comparator<Integer> counting(Comparator<Integer> c) {
        return (a, b) -> { compares.incrementAndGet(); return c.compare(a, b); };
    }

    public static void main(String[] args) {
        int n = 1000;
        for (String kind : List.of("sorted", "reverse", "random", "nearly", "equal")) {
            List<Integer> l = new ArrayList<>(gen(n, kind));
            compares.set(0);
            l.sort(counting(Comparator.naturalOrder()));
            System.out.printf("  %-10s %,d%n", kind, compares.get());
        }
    }

    static List<Integer> gen(int n, String kind) {
        List<Integer> l = new ArrayList<>();
        Random r = new Random(7);
        switch (kind) {
            case "sorted" -> { for (int i = 0; i < n; i++) l.add(i); }
            case "reverse" -> { for (int i = n; i > 0; i--) l.add(i); }
            case "random" -> { for (int i = 0; i < n; i++) l.add(r.nextInt(1_000_000)); }
            case "equal" -> { for (int i = 0; i < n; i++) l.add(5); }
            case "nearly" -> {
                for (int i = 0; i < n; i++) l.add(i);
                for (int k = 0; k < 10; k++) Collections.swap(l, r.nextInt(n), r.nextInt(n));
            }
        }
        return l;
    }
}

  sorted     999
  reverse    999
  random     8,673
  nearly     2,084
  equal      999

An already-sorted list costs exactly n - 1 comparisons: one pass finds a single ascending run and there is nothing to merge. A reverse-sorted list costs the same, because TimSort detects a strictly descending run and reverses it in place. Ten swaps in a sorted list of a thousand cost about a quarter of what full randomness costs. This is why re-sorting a list that is already mostly in order is cheap, and it is also why an expensive comparator hurts less than it looks on realistic data — and much more than it looks on random data.

Which one should you write?

Implementing Comparable is a commitment: it says this ordering is a property of the type, it will not change, and every sorted collection in the program will use it silently. If you would hesitate to write that sentence about your ordering, it is a Comparator.

Two practical habits. Make your comparator total — add a tie-break on a unique field so that equal-looking elements still have a defined order, otherwise the output depends on the input order and diffs churn. And build comparators out of comparing/thenComparing over key extractors rather than writing compare by hand, because that shape cannot be non-transitive.

FAQ

What is the difference between Comparable and Comparator in Java?

Comparable is implemented by the class being sorted and defines its single natural ordering through int compareTo(T o). Comparator is a separate object implementing int compare(T a, T b), defined outside the class, and you can have as many as you like. Collections.sort(list) uses the first; list.sort(comparator) uses the second.

Can a class have more than one Comparable?

No. Generic type arguments are erased, so implements Comparable<A>, Comparable<B> is a compile error: "Comparable cannot be inherited with different arguments". A second ordering has to be a Comparator.

Why does my sort throw "Comparison method violates its general contract!"?

Your comparator is not a valid ordering — most often it is not transitive, or it returns zero for pairs that are not interchangeable. TimSort detects the inconsistency while merging two runs and throws IllegalArgumentException rather than corrupt the array. It only detects it on inputs of 32 or more elements, and even then only sometimes, which is why the bug reaches production.

Why does subtracting two ints in a comparator not work?

a - b overflows when the difference exceeds the int range, and the wrapped result has the wrong sign — 2000000000 - (-2000000000) evaluates to -294967296. Use Integer.compare(a, b), or comparingInt, both of which are correct for every pair of int values.

Does reversed() only reverse the last key?

No. reversed() reverses the comparator it is called on, and in a chain that is everything to its left. comparing(dept).thenComparing(salary).reversed() sorts by department descending and salary descending. To reverse only the trailing key, write thenComparing(Employee::salary, Comparator.reverseOrder()).

How do I sort a list that contains nulls?

Wrap the comparator: list.sort(Comparator.nullsFirst(Comparator.naturalOrder())) for null elements. For null sort keys inside non-null elements, pass the wrapper as the second argument to comparing: comparing(Contact::nickname, nullsLast(naturalOrder())).

Is List.sort stable?

Yes. List.sort and Arrays.sort(Object[], Comparator) both run TimSort, which the javadoc guarantees to be stable. Arrays.sort on a primitive array is a dual-pivot quicksort and is not stable, but there is no comparator overload for primitives and two equal int values are indistinguishable, so nothing observable depends on it.

Why is there comparingInt as well as comparing?

comparing needs a key that is Comparable, so an int key is autoboxed twice per comparison and then compared through Integer.compareTo. comparingInt takes a ToIntFunction and calls Integer.compare on the raw values. Sorting a thousand records runs the key extractor 17,346 times, so that is 17,346 allocations avoided for a one-word change.

Conclusion

Comparable answers "what order does this type have", Comparator answers "what order does this call want", and the factory methods — comparing, comparingInt, thenComparing, reversed, nullsFirst — cover almost every ordering you will ever need without a hand-written compare body. That matters for correctness, not just brevity: comparators composed from key extractors are transitive by construction, and the two failures in this article, the int subtraction overflow and the non-transitive tolerance, are both things the factory methods make it hard to write.

Take away three rules. Compare with Integer.compare, never with subtraction. Remember that reversed() flips the whole chain. And when a sort throws IllegalArgumentException with that message, do not reach for the legacy merge sort flag — the comparator really is broken, and it was broken on your small test data too.

Next in this series: the Collections utility class — sort, reverse, shuffle, binarySearch, and the unmodifiable and synchronized wrappers that hide behind the same class.