Comparable and Comparator

Sorting in Java is two interfaces and one contract, and almost every problem with it is a contract violation rather than a bug in the sort. Comparable is a type's natural order; Comparator is an order imposed from outside. The contract is that the comparison must be consistent — and when it is not, a sort throws an exception with a message that names none of this, or a TreeMap quietly loses entries.

#Natural order, and order imposed

record Employee(String name, String team, int salary) implements Comparable<Employee> {
    @Override public int compareTo(Employee other) {
        return name.compareTo(other.name);          // the natural order
    }
}
 
list.sort(null);                                     // uses compareTo
list.sort(Comparator.comparingInt(Employee::salary));  // imposes another

A type has one natural order and it should be the obvious one — alphabetical for a name, chronological for a timestamp. Anything debatable is a Comparator, because there will be a second opinion and a type can only hold one.

The return value is a sign, not a magnitude: negative if this sorts first, zero if they tie, positive otherwise. Integer.compare(a, b) exists because the obvious a - b overflows — compare(Integer.MIN_VALUE, 1) as a subtraction is positive, which says the minimum sorts last.

#Building comparators

Comparator<Employee> byTeamThenPay =
        Comparator.comparing(Employee::team)
                  .thenComparing(Employee::salary, Comparator.reverseOrder())
                  .thenComparing(Employee::name);

Read it as written: team ascending, then salary descending inside a team, then name to break remaining ties. thenComparing is consulted only when everything before it returned zero.

Two details worth having:

• reversed() reverses everything before it. comparing(a).thenComparing(b).reversed() is not "a ascending, b descending" — it flips the whole thing. Put reverseOrder() on the specific key instead.
• Nulls need a decision. Comparator.nullsFirst(comparing(Employee::team)) says where a null sorts; without it a null field throws a NullPointerException from inside the sort, which is a confusing place to meet one.

The overflow is worth seeing rather than being told about:

java.util.Comparator<Integer> subtraction = (x, y) -> x - y;
System.out.println(subtraction.compare(Integer.MIN_VALUE, 1));
System.out.println(Integer.compare(Integer.MIN_VALUE, 1));

The subtraction says the smallest possible integer sorts after 1, as positively as it can. Nothing throws, the sort completes, and the answer is wrong in a way that only shows up on inputs far apart.

#The contract

A comparator must be, for all values:

1. Antisymmetric — compare(a, b) and compare(b, a) have opposite signs.
2. Transitive — if a < b and b < c then a < c.
3. Consistent — if compare(a, b) == 0 then compare(a, c) and compare(b, c) agree for every c.

Break transitivity and Arrays.sort may throw:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

That message is TimSort noticing that the order it built is impossible. It is a good error — it names a real defect — but it says nothing about which comparison was wrong, and it appears only on inputs large enough for TimSort to merge runs, so it typically reaches production rather than the test suite.

The usual causes are comparing on a mutable field that changed mid-sort, a hand-written chain with a missing case that returns zero by accident, and the subtraction overflow above.

#Consistency with equals, and the entries that vanish

This is the rule that is not enforced and costs the most.

compareTo returning zero should mean equals returns true. When it does not, a TreeSet and a TreeMap behave in a way that looks like data loss — because they use the comparator, not equals, to decide identity:

var byAge = new TreeSet<>(Comparator.comparingInt(Person::age));
byAge.add(new Person("Asha", 30));
byAge.add(new Person("Ravi", 30));
System.out.println(byAge.size());        // 1

Nothing is wrong here by the rules; TreeSet was told that age is what distinguishes people, and it believed it. The sorted collections lesson's exercise is this exact shape.

The fix is to end every comparator used for a sorted collection with a tie-break that is unique — .thenComparing(Person::name), or an id — so that zero means genuinely the same thing.

#Under the hood: which sort runs

Arrays.sort has two implementations, and which one you get depends on the element type.

Stable means equal elements keep their relative order, which is what lets you sort twice to get a compound order: sort by name, then by team, and within a team the names remain sorted. It is also why List.sort is safe to use for a "sort by the column the user clicked" feature.

TimSort finds runs that are already ordered and merges them, so nearly-sorted input is close to O(n). That is the reason it noticed the contract violation above at all: it builds on an assumption the comparator broke.

#Walkthrough: the leaderboard that threw on Fridays

A leaderboard sorted players by score, with a comparator that fell back to "most recently active" for ties. It threw IllegalArgumentException about once a week, always under load.

The fallback read player.lastSeen(), which a background thread updated as events arrived. During a sort long enough to matter, a player's lastSeen changed between two comparisons — so the sort had already placed them using one value and now compared them with another. TimSort merged two runs, found the order impossible, and threw.

Nothing was wrong with the comparator in isolation. It was wrong about the data being still.

The fix was to snapshot: copy the list and the fields being compared into a record before sorting. Sorting a moving target is not a sort.

#Try it yourself

var xs = new ArrayList<>(List.of("bb", "a", "ccc", "dd"));
xs.sort(Comparator.comparingInt(String::length).reversed());

var s = new TreeSet<>(Comparator.comparing(String::length));
s.add("cat"); s.add("dog"); s.add("emu");

Comparator<Item> a = (x, y) -> x.price() - y.price();
Comparator<Item> b = (x, y) -> x.price() < y.price() ? -1 : 1;

#Misconceptions

• "a - b is a comparator." It is one until the numbers are far apart, and then it silently inverts.
• "reversed() reverses the last key." It reverses the whole comparator built so far.
• "Equal means equals." For TreeSet and TreeMap, equal means the comparator returned zero. For HashSet it means equals.
• "The contract exception is a JDK bug." It is TimSort reporting that no consistent order exists for the comparator it was given.
• "Sorting is stable." For objects, yes. For primitive arrays, no, and it does not matter there.

#Going deeper

• Comparator's javadoc — the factory methods and the exact wording of the contract.
• java.util.TimSort in the JDK, and the note on why the contract check exists.
• Effective Java item 14, on implementing Comparable, and item 10 on the equals contract it has to agree with.